c语言实现八大排序

c语言实现八大排序

插入排序

思想：插入排序就是从第二个数开始（因为第一个数后面已经没有数了，不用进行比较），往后遍历比较，遇到比它大的则继续往后，当遇到比它小的，则将前面的数全部往后挪动，将这个数插入在比它小的前面，然后继续从第三个数开始，再往后比较

动图演示：

 代码演示：

void insersort(int* a, int n) {for (int i = 0; i < n-1; i++) {int end = i; //定义end为选择的数的后一位int tmp = a[end + 1];//将选择的数保存起来while (end >= 0) {//当end没有越界时if (tmp < a[end]) {//如果后面的数比选择的数大a[end + 1] = a[end];//往后挪动end--;//end指针往前移动}else//当end指向的数比选择的数小时，停止移动{break;}}a[end + 1] = tmp;//将选择的数插入}
}

希尔排序

思想：希尔排序是属于插入排序的一种优解，当数组为从大到小排序，而我们需要将这个数组从变成从小到大排序时，插入排序的时间将会达到最大，此时希尔排序则能有效地优化插入排序，我们定义一个gap的数，然后从0开始将间距为gap的数进行插入排序，然后再从0+1开始将间距为gap的数进行插入排序，一直循环gap-1次（也就是从0到gao-1开始的间距为gap的数都进行插入排序），这是第一趟排序，第二趟则将gap减小再次进行排序，第三第四趟也是如此，上述的排序称为“预排序”

那么当gap＝1时，数组已经接近有序了，此时再进行一次排序（gap＝1时，其实就是将数组的全部元素进行一次插入排序），数组就是有序了。

这是大佬对于希尔排序的解释：

图解：

那么，怎么选择gap的值呢，有几种方法：gap=[n/2]或者gap=[n/3]，那么如何让最后一次的gap等于1呢？gap=[n/2]时，gap最终都会＝1，gap=[n/3]时，gap有可能会变成0，所以可以令gap=[n/3 +1 ]，这样gap最后总是会等于1

所以，gap可以取 [n/2]或者[n/3 +1]，这里我们选用后一种 gap=[n/3+1]

代码：

第一种是用两个for循环进行排序，最里面的一层for循环是对间隔为gap的数组进行插入排序，外面一层for循环是从0到gap之间的起始数开始循环，外面的while则是令gap不断减小，直到等于1则停止循环。

void shellsort1(int* a, int n) {int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int j = 0; j < gap; j++) {for (int i = 0; i < n - gap; i += gap) {int end = i;int tmp = a[end + gap];while (end >= 0) {if (tmp < a[end]) {a[end + gap] = a[end];end -= gap;}else {break;}}a[end + gap] = tmp;}}}
}

 第二种则在第一种的情况下优化了一下，只进行了一次for循环，但是外内各有一层while，for循环则控制起始坐标从0到gap之间，里面的while则是让间距为gap之间的数进行插入排序，而这些数最后都会在数组内，所以条件则为当最后一个数的数组越界之后则停止插入排序，最外面的while则同样的对gap进行调整。

void shellsort2(int* a, int n) {int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++) {int end = i;int tmp = a[end + gap];while (end >= 0) {if (tmp < a[end]) {a[end + gap] = a[end];end -= gap;}else {break;}}a[end + gap] = tmp;}}
}

选择排序

思想：选择排序较为简单粗暴，遍历一边数组，选出最小的，放到第一位，从第二位开始遍历，选出最小的，放到第二位，从第三位开始遍历，选出最小的，放到第三位，以此类推

动图演示：

 代码：

void selectsort(int* a, int n) {int mini = 0;int tmp = 0;for (int i = 0; i < n-1; i++) {int min = a[i];for (int k = i; k < n; k++) {if (a[k] < min) {min = a[k];mini = k;}}tmp = a[i];a[i] = min;a[mini] = tmp;}
}

堆排序

堆排序在之前的文章中已经顺带介绍过了，下面有链接可以跳转进去。

堆排序

 图解：

 这里提醒一下，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

假设需要排升序，那么数组则是从小到大的，如果排的是小堆，那么堆顶的元素则为最小的，然后我们需要忽略掉第一个元素，从第二个元素开始作为堆顶重新做堆，那么此时大家的关系有可能都会乱套，那么就需要重新建堆，每排一次都要建一次堆，这不行，很麻烦且复杂且时间复杂度高

假如我们排的是大堆，那么堆顶的元素则为最大的，我们将堆顶的元素与堆尾的元素进行交换，并且忽略掉倒数第一个元素，然后将交换后的堆顶进行向下调整，那么此时堆则不会被破坏，而最后一个数也为最大的，符合升序，然后再将次大的与倒数第二个数进行交换，反复进行，最后就拍完序了，那么降序也是一样，需要建小堆

所以，结论就是排升序要建大堆，排降序建小堆。

代码思路：假设需要升序，那么将乱序数组建堆，建成大堆，然后令堆顶与堆尾交换，然后忽略掉倒数第一个元素，然后对堆顶进行向下调整，第二次第三次以此类推。

建堆需要用到向上调整算法

而向上调整算法与向下调整算法都在上面给出链接，希望读者能结合两处情况进行考虑

冒泡排序

思想：相信冒泡排序很多人都会学过，原理就是不断地选取较大的数与后面的数进行比较，遇到较小数则进行交换，当遇到更大的数则选取更大的数，然后继续和后面的数进行比较

动图演示：

代码：

void bubblesort(int* a, int n) {int tmp = 0;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n - 1 - i; j++) {if (a[j] > a[j + 1]) {tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}
}

快速排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

而快速排序从出现到现在，有着三种不同的方法

第一种：hoare版

思想：定义左指针left与右指针right，首先将左边第一个数定为key，然后右边开始往前走，遇到比key小的数，则停止，然后左边开始走，遇到比key大的数，则停止，然后将左右两数进行交换，然后右边继续先走，然后再到左边，一直反复，直到left与right相遇，然后令key与right的值进行交换，然后令此时left与right相遇的值与下标重新定义为key，然后此时由key将数组分割成两份，左数组为[0,key-1],而右数组为[key+1,n-1]此时，第一次排序已经完成，然后再对左数组看成一个新的数组重新排序，以此类推，不断地递归，那么停止的标准就是当最开始的begin≥end，也就是数组的开头≥尾的时候就可以停止分割停止排序了

代码：

void quicksort(int* a, int begin, int end) {if (begin >= end) {return;}/*1.左右指针法*/int left = begin;int right = end;int key = left;int tmp = 0;while (left < right) {while (a[right] > a[key] && left < right) {right--;}while (a[left] < a[key] && left < right) {left++;}tmp = a[left];a[left] = a[right];a[right] = tmp;}tmp = a[key];a[key] = a[right];a[right] = tmp;key = left;quicksort(a, begin, key - 1);//左边递归quicksort(a, key + 1 , end);//右边递归
}

 需要注意到的问题

要知道，左指针是找比key大的值，右指针是找比key小的值，而左指针先动，那么右指针是一定要跟着动，如果右指针先动，那么左指针也一定要跟着动，也就是说，左右指针无论谁先动，都一定要动完整个周期（左->右或者右->左），

如果左侧先动的话，无法保证相遇时对应的数比key小，那么最后交换key的时候就会产生错误，右侧先动的话，右指针的时候就一定会停在比key小的地方，然后左指针开始移动就一定相遇在比key小的值，这就是为什么一定要右指针先走动

第二种：挖坑法

思想：也是定义左指针left与右指针right，key对应的下标为piti，然后将左边第一个元素放到key里面，然后此时左边就有了坑，然后右边开始往前走，遇到比key小的，则与key交换，那么此时右指针的地方则变成新坑，然后左边走，左边遇到比key大的数则交换，然后左边变成新坑，以此类推，当相遇时停止，然后将key放进相遇的坑位，然后分割成两个左右数组，左数组为[0,piti-1],而右数组为[piti+1,n-1]，然后就是一样的对左右数组进行重新排序，不断地递归

动图演示：

 代码：

void quicksort(int* a, int begin, int end) {if (begin >= end) {return;}int key = a[begin];int piti = begin;while (begin < end) {//左边是坑，右边找小填坑，然后右边成为新的坑while (begin < end && a[end] >= key) {end--;}a[piti] = a[end];piti = end;///右边是坑，左边找小填坑，然后左边成为新的坑while (begin < end && a[begin] <= key) {begin++;}a[piti] = a[begin];piti = begin;}//当相遇时a[piti] = key;quicksort(a, begin, piti - 1);//左边递归quicksort(a, piti + 1 , end);//右边递归
}

 第三种：前后双指针法

思想：定义左边第一个数为key，然后定义前指针cur，与后指针prev=cur+1，首先判断cur指针的值，如果比key小，那么prev往后挪，如果prev等于cur，那么cur往后挪，如果cur的值大于key，那么prev不动，cur往后挪，然后当遇到比key小的值，那么prev的后一位就是比key大的，此时prev往后挪然后将prev的值与cur的值交换即可，一直到最后，cur到达尾部时停止循环，然后将key的值与prev对应的值交换，此时prev的值则为key，prev也将两个数组分割成左右两个数组，然后进行递归

动图演示：

代码：

void quicksort(int* a, int begin, int end) {if (begin >= end) {return;}int prev = begin;int key = begin;int cur = begin + 1;int tmp = 0;while (cur <= end) {if (a[cur] < a[key]) {prev++;if (prev != cur) {tmp = a[prev];a[prev] = a[cur];a[cur] = tmp;cur++;}}cur++;}tmp = a[key];a[key] = a[prev];a[prev] = tmp;key = prev;quicksort(a, begin, key - 1);//左边递归quicksort(a, key + 1 , end);//右边递归
}

 快速排序优化

前面三种的key都不约而同地将左边第一个值当成key，假如最左边的数是一个极端值（为数组中最大或者最小的），那么此时将会是最复杂的一种情况

那么此时我们的key可以使用三数取中法确定

三数取中代码：

int getmidindex(int* a, int begin, int end) {int mid = (begin + end) / 2;//先去数组中间的下标if (a[begin] < a[mid]) {//假设头值<中间值if (a[mid] < a[end]) {//如果中间值<尾值，那么则 a[begin]<a[mid]<a[end]return mid;}else if (a[begin] < a[end]) {//如果头值小于尾指,隐含条件a[mid]>a[end]，此时a[begin]<a[end]<a[mid]return end;}else{return begin;//此时上述条件都不满足，那么只有begin的值为三个数的中值}}else//隐含条件a[begin] > a[end]，下面的条件与上述基本相同{if (a[mid] > a[end]) {return mid;}else if (a[begin] < a[end]) {return begin;}else{return end;}}
}

 当数组递归到较小区间时可以使用插入排序

上述三种方法都需要用到递归，不断地递归到小的数组且接近有序，此时插入排序的优点就体现出来了

归并排序

思想：归并排序可以看成一种分治的思想，就是对数组不断地分割，分割成不可再分割的数组，然后再进行排序递归

动图演示：

 代码：

//归并排序主函数
void _mergesort(int* a, int begin, int end, int* tmp) {if (begin >= end) {//当分割到剩下一个或者不存在时停止递归return;}int mid = (begin + end) / 2;_mergesort(a, begin, mid, tmp);//不断地分割左数组_mergesort(a, mid + 1, end, tmp);//不断地分割右数组int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin1;while (begin1 <= end1 && begin2 <= end2) {//此时可以进行两数组合并成一个数组，不断地比较，将两数组中小的放进新创的数组，直到两个数组都放完进去，当有一个数组放完之后停止循环if (a[begin1] < a[begin2]) {tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1) {//因为从小数组的时候已经为有序，那么辅助数组也有序，剩下的数组也有序，那么只需要直接放进去就好了tmp[i++] = a[begin1++];}while (begin2 <= end2) {tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));//将排序后的辅助数组全部复制进原来的数组，然后返回上一层递归
}
//归并排序前置
void mergesort(int* a,int n) {int* tmp = (int*)malloc(sizeof(int) * n);//创建一个用来辅助归并的数组if (tmp == NULL) {printf("malloc failn");exit(-1);}_mergesort(a, 0, n - 1, tmp);//进入递归free(tmp);
}

计数排序

思想：计数排序就是将出现过的元素使用相对映射统计一边，然后重新放回数组里，这种方法比较适合范围较集中的数组

动图演示：

代码：

void countsort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 1; i < n; i++) {      //遍历确定范围if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);memset(count, 0, sizeof(int) * range);if (count == NULL){printf("malloc failn");exit(-1);}// 统计次数for (int i = 0; i < n; i++){//使用相对映射，这样就不用担心值与下标有冲突的情况，也可以解决负数的问题count[a[i] - min]++;}// 根据次数，进行排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

复杂度与稳定性

稳定性是指，排序的过程中，对于同样的值不会改变先后位置，比如说a=3，b=3吗，a的下标为1，b的下标为2，a在b的前面，排完序之后，a的下标仍然比b的下标要小，也就是a始终在b的前面，那么就是稳定的情况，如果改变了先后位置，那么就是不稳定

排序方式	最好情况	最坏情况	平均情况	空间复杂度	稳定性
插入排序	O(N)	O(N^2)	O(N^2)	O(1)	稳定
希尔排序	O(N^1.3)	O(N^2)	O(N*logN)~O(N^2)	O(1)	不稳定
选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不稳定
冒泡排序	O(N^2)	O(N^2)	O(N^2)	O(1)	稳定
快速排序	O(N*logN)	O(N^2)	O(N*logN)	O(logN~N)	不稳定
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(N)	稳定
计数排序	O(max(range,N)	O(max(range,N)	O(max(range,N)	O(range)	不稳定