常用排序算法介绍与实现详解程序员

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

下面来介绍几种简单而且经典的排序算法，这是测试用的主函数，各个排序算法在vs2013下全部测试通过

int main() 

 int a[10] = { 6, 4, 5, 7, 1, 2, 9, 3, 8, 10 }; 

 int n = 10; 

 int i; 

 quick_sort(a, 0, 9); //替换这里即可 

 for(i = 0; i i++){ 

 printf("%d ", a[i]); 

 return 0; 

}

冒泡排序：

冒泡排序是非常容易理解和实现，，以从小到大排序举例：

设数组长度为N。

1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。

3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

下面是实现代码：

void bubblesort(int a[], int n){ 

 int j, k; 

 int flag,temp; 

 flag = n; 

 while (flag 0){ 

 k = flag; 

 flag = 0; 

 for (j = 1; j j++) 

 if(a[j-1] a[j]){ 

 temp = a[j - 1]; 

 a[j - 1] = a[j]; 

 a[j] = temp; 

 flag = j; 

}

直接插入排序：

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

直接插入排序示意图：

 

设数组为a[0…n-1]。

1.  初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2.  将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3.  i++并重复第二步直到i==n-1。排序完成。

下面是具体实现代码

void insertsort(int a[], int n){ 

 int i, j; 

 int temp; 

 for (i = 1; i i++){ 

 if (a[i] a[i - 1]){ 

 temp = a[i]; 

 for (j = i - 1; j = n - 1 a[j] temp; j--) 

 a[j + 1] = a[j]; 

 a[j + 1] = temp; 

}

希尔排序：

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

 

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

 

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49  38   65   97   26   13   27   49   55   4

1A    1B

  2A 2B

 3A 3B

  4A 4B

  5A 5B

1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26)，下同。

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4   49   38   65   97   26

1A   1B   1C   1D   1E

  2A 2B   2C   2D   2E

第三次 gap = 2 / 2 = 1

4  26  13  27  38  49  49  55  97  65

1A  1B 1C 1D 1E 1F 1G 1H 1I 1J

第四次 gap = 1 / 2 = 0 排序完成得到数组：

4  13  26  27  38  49  49  55   65  97

下面是具体实现代码：

void shellsort(int a[],int n){ 

 int j,k, gap; 

 for (gap = n / 2; gap gap /= 2) 

 for (j = gap; j j++) 

 if (a[j] a[j-gap]){ //每个元素与自己的组进行直接插入排序 

 k = j - gap; 

 int temp = a[j]; 

 while (k 0){ 

 a[k+gap] = a[k]; 

 k -= gap; 

 a[k + gap] = temp; 

}

归并排序：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

其基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

归并排序示意图

下面是实现代码：

//将有二个有序数列a[first...mid]和a[mid...last]合并。 void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i = m j = n) { if (a[i] = a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i = m) temp[k++] = a[i++]; while (j = n) temp[k++] = a[j++]; for (i = 0; i i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左边有序 mergesort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //再将二个有序数列合并 } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; return true; } 

选择排序：

选择排序的核心思想是：

第 i 趟排序是从后面的 n i + 1（i = 1，2，3，4，. . .，n 1）个元素中选择一个值最小的元素与该 n i + 1 个元素的最前门的那个元素交换位置，即与整个序列的第 i 个元素交换位置。如此下去，直到 i = n 1，排序结束。

也可描述为：

每一趟排序从序列中未排好序的那些元素中选择一个值最小的元素，然后将其与这些未排好序的元素的第一个元素交换位置。

特点：

1. 算法完成需要 n 1 趟排序，按照算法的描述，n 1 趟排序之后数组中的前 n 1 个元素已经处于相应的位置，第 n 个元素也处于相应的位置上。

2. 第 i 趟排序，实际上就是需要将数组中第 i 个元素放置到数组的合适位置，这里需要一个临时变量 j 来遍历序列中未排好序的那些元素，另一临时变量 d 来记录未排好序的那些元素中值最小的元素的下标值，

3. 一趟遍历开始时，令 d = i，假定未排序序列的第一个元素就是最小的元素，遍历完成后，变量 d 所对应的值就是值最小的元素，判断 d 是否是未排序序列的第一个元素，如果是，则不需要交换元素，如果不是，则需要交换array[d] 和 array[i]。

4. 此方法是不稳定排序算法，可对数组{a1 = 49，a2 = 38, a3 = 65, a4 = 49, a5 = 12, a6 = 42} 排序就可以看出，排序完成后 a1 和 a4的相对位置改变了。

5. 此方法移动元素的次数比较少，但是不管序列中元素初始排列状态如何，第 i 趟排序都需要进行 n i 次元素之间的比较，因此总的比较次数为

1 + 2 + 3 + 4 +5 + . . . + n 1 = n(n-1)/2, 时间复杂度是 O(n^2).

选择排序示意图：

快速排序：

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
3）从j开始向前搜索，即由后开始向前搜索(j )，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。
我们取走了下标0的数据，于是，我们需要找到一个数字来替换他。由于我们要把所有比6小的数移动到左面，所以我们可以开始寻找比6小的数并从右往左找。别急，我们要按顺序找哦。不断递减j的值，我们发现下标3的数据比6小，于是把3移到下标0（实际是i指向的位置。代码中要用i，因为后面还会循环这个步骤，不用i的话第二次循环：
由于变量k已经储存了下标0的数据，所以我们可以放心的把下标0覆盖了。如此一来，下标3虽然有数据，但是相当于没有了，因为数据已经复制到别的地方了。于是我们再找一个数据来替换他。这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2是第一个比k大的，于是用下标2的数据7替换j指向的下标3的数据，数据状态变成下表：
重复上面的步骤，递减变量j。这时，我们发现i和j“碰头”了：他们都指向了下标2。于是，循环结束，把k填回下标2里，即得到结果。
如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
注意：快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。（你可以想象一下i和j是两个机器人，数据就是大小不一的石头，先取走i前面的石头留出回旋的空间，然后他们轮流分别挑选比k大和比k小的石头扔给对面，最后在他们中间把取走的那块石头放回去，于是比这块石头大的全扔给了j那一边，小的全扔给了i那一边。只是这次运气好，扔完一次刚好排整齐。）为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

   实现代码：

void quick_sort(int s[], int l, int r) 

 if (l r) 

 //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1 

 int i = l, j = r, x = s[l]; 

 while (i j) 

 while(i j s[j] = x) // 从右向左找第一个小于x的数 

 j--; 

 if(i j) 

 s[i++] = s[j]; 

 while(i j s[i] x) // 从左向右找第一个大于等于x的数 

 i++; 

 if(i j) 

 s[j--] = s[i]; 

 s[i] = x; 

 quick_sort(s, l, i - 1); // 递归调用 

 quick_sort(s, i + 1, r); 

}

快速排序是一种很基础而且很重要的算法，无论考试还是面试中都会经常看到它，所以熟练掌握是必须的。

7290.html

服务器部署程序员系统优化网站设置运维