八种排序原理及其C语言代码

稳定排序和不稳定排序

      首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

      其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。

回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

(3)插入排序 

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

(4)快速排序 

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序 

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

(6)基数排序 

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

(7)希尔排序(shell) 

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

(8)堆排序 

我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

前7中排序，C语言实现：

#include <cstdio> void bubble(int v[], int n)//1冒泡排序 { for (int i = 1; i<n; i++) // i循环决定了冒泡的趟数是 n-1 { for (int j = 0; j<n - i; j++) //j 循环确定了每一趟的比较次数为 n-i { if (v[j]>v[j + 1]) { v[j] = v[j] ^ v[j + 1]; v[j+1] = v[j] ^ v[j + 1]; v[j] = v[j] ^ v[j + 1]; } } } } void select_sort(int v[], int len)//2,选择排序,找出最小的放在最前面 { for (int i = 0; i<len-1; i++) { int min = i; for (int j = i + 1; j<len; j++) min = v[min]>v[j] ? j : min; v[i] = v[i] ^ v[min]; v[min] = v[i] ^ v[min]; v[i] = v[i] ^ v[min]; } } void insert(int V[],int len)//3,插入排序 { for (int i = 1; i<len; i++) { int end = V[i]; int j; for ( j = i - 1; end<V[j] && j >= 0; j--)//找到合适位置之前把值依次向后移动。 V[j + 1] = V[j]; V[j + 1] = end ; } } void quickSort(int s[], int l, int r) //4,快速排序 { if (l< r) { 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; quickSort(s, l, i - 1); // 递归调用 quickSort(s, i + 1, r); } } int maxbit(int data[], int n) //辅助函数，求数据的最大位数 { int d = 1; //保存最大的位数 int p = 10; for (int i = 0; i < n; ++i) { while (data[i] >= p) { p *= 10; ++d; } } return d; } void radixsort(int data[], int n) //基数排序 { int d = maxbit(data, n); int *tmp = new int[n]; int *count = new int[10]; //计数器 int i, j, k; int radix = 1; for (i = 1; i <= d; i++) //进行d次排序 { for (j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for (j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; } for (j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for (j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; } delete[]tmp; delete[]count; } void Merge(int arr[], int reg[], int start, int end) { if (start >= end)return; int len = end - start, mid = (len >> 1) + start; //分成两部分 int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; //然后合并 Merge(arr, reg, start1, end1); Merge(arr, reg, start2, end2); int k = start; //两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较 //如此反复,可以把两个有序的序列合并成一个有序的序列 while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; //然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环 //那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放 while (start1 <= end1) reg[k++] = arr[start1++]; //这一步和上面一样 while (start2 <= end2) reg[k++] = arr[start2++]; //把已经有序的reg序列放回arr序列中 for (k = start; k <= end; k++) arr[k] = reg[k]; } void MergeSort(int arr[], const int len) { //创建一个同样长度的序列,用于临时存放 int *reg = new int[len]; Merge(arr, reg, 0, len - 1); delete[] reg; } void shell_sort(int a[], int n) { int gap; for (gap = 3; gap >0; gap--) { for (int i = 0; i<gap; i++) { for (int j = i + gap; j<n; j = j + gap) { if (a[j]<a[j - gap]) { int temp = a[j]; int k = j - gap; while (k >= 0 && a[k]>temp) { a[k + gap] = a[k]; k = k - gap; } a[k + gap] = temp; } } } } } void print(int V[],int len) { for (int i = 0; i<len; i++) { printf("%d ", V[i]); } printf("\n"); } int main() { int a1[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; int len = sizeof(a1) / sizeof(int); print(a1, len); bubble(a1, len); print(a1, len); int a2[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; select_sort(a2, len); print(a2, len); int a3[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; insert(a3, len); print(a3, len); int a4[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; quickSort(a4, 0,len-1); print(a4, len); int a5[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; MergeSort(a5, len); print(a5 ,len); int a6[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; radixsort(a6, len); print(a6, len); int a7[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; shell_sort(a7, len); print(a7, len); } 单独的堆排序实现： #include <stdio.h> #include <stdlib.h> #include <assert.h> static void heap_arrange(int arr[], int cur, int size); static int heap_verify(int arr[], int size) { int i; for (i = 0; i < size / 2; ++i) { int lhs = 2 * i + 1; int rhs = 2 * i + 2; if (lhs < size && arr[i] > arr[lhs]) { fprintf(stderr, "arr[%d]:%d > arr[%d]:%d\n", i, arr[i], lhs, arr[lhs]); return -1; } if (rhs < size && arr[i] > arr[rhs]) { fprintf(stderr, "arr[%d]:%d > arr[%d]:%d\n", i, arr[i], rhs, arr[rhs]); return -1; } } return 0; } static void heap_print(int arr[], int size) { int layer = 0, num = 0; for (layer = 0; num < size; ++layer) { int i = 0; for (i = 0 ; i < (1 << layer) && num < size ; ++i) printf("= ", arr[num++]); printf("\n"); } } // 调整为小顶堆 static void heap_arrange(int arr[], int cur, int size) //调整为小顶堆 { while (cur < size) { int left = 2 * cur + 1; int right = 2 * cur + 2; int min = -1; int min_val = arr[cur]; if (left < size && arr[left] < min_val) { //检查是否比左节点大 min = left; min_val = arr[left]; } if (right < size && arr[right] < min_val) {//检查是否比右节点大 min = right; min_val = arr[right]; } if (min == -1) { printf("当前点%d，左子树：%d,右子树%d.合理退出\n" ,arr[cur],arr[left] ,arr[right]); break; } int heaptop_val = arr[cur]; //堆顶的值 arr[cur] =min_val; arr[min] = heaptop_val; cur = min; printf("交换%d\n",min_val); heap_print(arr, size); } } static void heap_sort(int arr[], int size) { int i; for (i = size / 2-1 ; i >= 0; --i) { heap_arrange(arr, i, size); // 建堆 } printf("make heap:\n", i); heap_print(arr, size); assert(heap_verify(arr, size) == 0); for (i = size - 1; i > 0; --i) { int tmp; tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; //arr[i]<-->arr[size-1] printf("sort i=%d\n", i); heap_print(arr, size); heap_arrange(arr, 0, i);//建堆 heap_print(arr, size); assert(heap_verify(arr, i) == 0); } printf("sorted:\n"); heap_print(arr, size); } static int input(int **arr, int *size) { int i; int ret; printf("输入变量个数:\n"); ret = fscanf(stdin, "%d", size); //if (ret != 1) // return -1; printf("输入变量:\n"); *arr = (int *)malloc(sizeof(int) * (*size)); for (i = 0; i < *size; ++i) { fscanf(stdin, "%d", &(*arr)[i]); } return 0; } int main(int argc, char *argv[]) { int *arr = NULL; int size = 0; int i; if (input(&arr, &size) < 0) { fprintf(stderr, "input error\n"); return 0; } printf("origin:\n"); heap_print(arr, size); heap_sort(arr, size); return 0; }