首页 > > 程序设计 > C/C++ >

2 程序中的各类排序算法

2018-06-18 04:08:10来源：未知阅读 ()

1、冒泡排序

冒泡排序算法的运作如下：

（1）临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,

（2）这样一趟过去后,最大或最小的数字被交换到了最后一位,

（3）然后再从头开始进行两两比较交换,直到倒数第二位时结束。

冒泡排序总的平均时间复杂度为

 1 void bubble_sort(int a[], int n)
 2 {
 3     int i, j, temp;
 4     for (j = 0; j < n - 1; j++)
 5     {
 6         for (i = 0; i < n - 1 - j; i++)
 7         {
 8             if(a[i] > a[i + 1])
 9             {
10                 temp = a[i];
11                 a[i] = a[i + 1];
12                 a[i + 1] = temp;
13             }
14         }
15     }
16 }

View Code

2、快速排序

快速排序是对冒泡排序的一种改进，它的基本思想是：
       通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序
过程可以递归进行，以此达到整个数据变成有序序列。
       设要排序的数组是A[0]... ... A[N-1]，首先任意选取一个数据作为关键数据，然后将所有比它小的数据都放到它前面，所有比它大的数据都放到它后面，这个过程称为一趟
快速排序。
      值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

 1 int FindPos(int *a, int low, int high)
 2 {
 3     int val = a[low];
 4     
 5     while (low < high)
 6     {
 7         while ((low < high) && (a[high] >= val))
 8         {
 9             --high;
10         }
11         a[low] = a[high];
12         
13         while ((low < high) && (a[low] <= val))
14         {
15             ++low;
16         }
17         a[high] = a[low];
18     }    
19     a[low] = val;
20     
21     return high;
22 }
23 
24 void QuickSort(int *a, int low, int high)
25 {
26     int pos;
27     
28     if (low < high)
29     {
30         pos = FindPos(a, low, high);
31         QuickSort(a, low, pos-1);
32         QuickSort(a, pos+1, high);
33     }
34 }

View Code

3、插入排序

插入排序算法的运作如下：

（1）

4、希尔排序

希尔排序算法的运作如下：

（1）

5、选择排序

选择排序算法的运作如下：

　　设有10个元素a[1]~a[10]，将a[1]与a[2]~a[10]比较，若a[1]比a[2]~a[10]都小，则不进行交换。若a[2]~a[10]中有一个以上比a[1]小，则将其中最小的一个与a[1]
交换，此时a[1]中存放了10个中最小的数。第二轮将a[2]与a[3]~a[10]比较，将剩下的最小者与a[2]对换，此时a[2]中存放的是10个中第二小的数，依此类推。

 1 for (i = 0; i < 9; i++)
 2 {
 3         min = i;
 4         for (j = i+1; j < 10; j++)
 5         {
 6     if (a[min] > a[j])
 7     {
 8                         min = j;
 9     }
10         }
11         temp = a[i];
12         a[i] = a[min];
13         a[min] = temp;
14 }