在开始之前先准备一个交换数据的函数，排序会经常用到

//交换位置
Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}

一、 冒泡排序

左右相邻进行比较，最大的或者最小的交换到两边

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){// 单趟int flag = 0;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0)//判断是否全部排序完成{break;}}
}

二、 选择排序

如图所示，找到最小值，放在最前面，前面的N个数据默认为有序，就从N后继续开始排序
不过在下面的代码中我进行了改进，遍历一次找到最大和最小值放在两侧，提高效率

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin + 1; i <= end; i++){if (max < a[i]){max = i;}if (min > a[i]){min = i;}}Swap(&a[begin], &a[min]);if (max == begin){max = min;}Swap(&a[end], &a[max]);begin++;end--;}
}

为什么要加

if (max == begin){max = min;}

就是怕遇到如上图这种情况

三、插入排序

数据从后向前进行对比，如果找到大于自己的就继续往前对比，找到小于的就插入进去

// 插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end+1] = tmp;}}

四、 快速排序

1. hoare版本

int PartSort1(int* a, int left, int right)
{//单趟if(left >= right)return;int keyi = left;int begin = left, end = right;while (begin < end){// 右边找小while (begin < end && a[end] >= a[keyi])//begin < end防止越界{--end;}// 左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);//交换l与r相遇位置和key的位置keyi = begin;//方便分割区间PartSort1(a, left, keyi - 1);//左区间PartSort1(a, keyi + 1, right);//右区间return begin;
}

2. 优化版本

上面hoare的版本在数据有序的情况下，会尴尬很多，我们的key每次都是最小值或者最大值，递归的深度就会变成N。
所以为了避免这种情况发生，我们key需要是一个接近中位数的值。

两种方法

1. 随机数选key
2. 三数取中

那我这里就以三数取中为例：
left、right、mid，三个数进行对比，取大小在中间的那个值。

int GetMid(int* a,int left, int right)//三数取中
{int mid = (left + right) / 2;if (a[left] > a[mid]){if (a[mid] > a[right])//left最大，right最小{return mid;}else if (a[left] < a[right]){return left;}elsereturn right;}else//a[left] < a[mid]{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}elsereturn right;}}void QuickSort(int* a, int left, int right)
{if (left >= right)return;//小区间优化if ((right - left + 1) <= 10){InsertSort(a+left, right - left + 1);}else{int mid = GetMid(a, left, right);//三数取中Swap(&a[left], &a[mid]);int key = left;int begin = left;int end = right;while (begin < end){//走边找小if (begin < end && a[end] >= a[key]){end--;}//左边找大if (begin < end && a[begin] <= a[key]){begin++;}Swap(&a[end], &a[begin]);}Swap(&a[key], &a[begin]);//交换l与r相遇位置和key的位置key = begin;//方便分区间QuickSort(a, left, key - 1);//左区间QuickSort(a, key + 1, right);//右区间}}

这里还没有结束，可以再优化一下，在我们进行快排的时候，如果每次的区间都能二分的化，这个递归的过程是可以看出一颗二叉树，而在满二叉树的叶子节点个数为整棵树的一半，对于快排来说它的最后一层和倒数第二层，是不用去排和只排一个数的，但是却还要开辟栈帧，所以我们这里使用小区间优化带代码如下直接使用当区间小于等于10时进行插入排序。

void QuickSort(int* a, int left, int right)
{if (left >= right)return;//小区间优化if ((right - left + 1) <= 10){InsertSort(a+left, right - left + 1);//每次递归会有偏移，所以要加上偏移量left}else{//递归……}
}

3. 前后指针法

通过动图我们可以判断出，当cur找到小于key的值，prev++，当++prev != cur，就会进行交换，当cur越界时，再把key和prev进行交换

//快速排序前后指针法
int PartSort1(int* a, int left, int right)
{int mid = GetMid(a, left, right);//三数取中Swap(&a[left], &a[mid]);int key = left;int prve = left;int cur = prve + 1;while (cur <= right){if (a[cur] < a[key] && ++prve != cur)Swap(&a[prve], &a[cur]);cur++;}Swap(&a[key], &a[prve]);return prve;
}

4. 非递归版本

快速排序其实跟二叉树的前序遍历非常相似，都是深度优先遍历。
快速排序非递归可以用栈实现，因为栈是后进先出所以要先把右区间的数压进栈

//快排非递归方法,用栈实现
#include "Stack.h"
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st));{int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int key = PartSort1(a, begin, end);//使用上面的前后指针法辅助单趟排序//[begin,key - 1] key [key + 1, end]if (key + 1 < end){StackPush(&st, end);StackPush(&st, key + 1);}if (key - 1 > begin){StackPush(&st,key - 1);StackPush(&st,begin);}}StackDestroy(&st);
}

五、 堆排序

我们建堆的时候，如果想要实现降序，那么我们应该建小堆，而不是大堆，因为如果我们建了大堆，只是堆成了降序，并不是原来的数组成了降序，升序相反建大堆。

void HeapSort(int* a, int max)//max为最大个数
{//建堆for (int i = 0; i <max; i++){AdjustUp(a, i);//模拟插入建小堆}//排序int end = max - 1;//找到最后一个元素的下标进行交换while (end>0){Swap(&a[0], &a[end]);AdjustDown(a, 0, end);--end;//最后的有序不再排序}
}

这里还可以再优化，降低时间复杂度

/*建堆方法一for (int i = 1; i < n; i++){AdjustUp(a, i);}*///建堆方法二for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从第一个非叶子节点调整{AdjustDown(a, n, i);} int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

六、 希尔排序

第一步：预排序
第二步：插入排序

1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
以gap==3为例

// 希尔排序
void ShellSort(int* a, int n)
{/*int gap = 3;*///第一种方法：一组一组gap走/*for (int j = 0; j < gap; j++){for (int i = j; 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 (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;}*/

当gap等于1时，和插入排序一摸一样

为什么i<n-gap呢

如图所示，为了防止tmp越界

这里我们可以总结出，在预排序阶段
gap越大，大的可以越快跳到后面，小的可以越快跳到前面，但是越不接近有序
gap越小，跳的就越慢，但是更接近有序。

所以，还可以再优化一下

	//第三种方法：优化一下gap = gap / 3 + 1；int gap = n;while (gap > 1){for (int i = 0; i < n - gap; ++i){gap = gap / 3 + 1;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;}}
}

在这个方法中，当gap > 1时是预排序，gap == 1时是插入排序

七、 归并排序

归并排序的思想就是分治法(分而治之)

1. 递归版本

如果在原数组上进行比较交换，会导致数据被覆盖，所以我们开辟一个tmp数组，来存放交换结果，再返回给原数组
下面的代码就像是二叉树的后序遍历

void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)//返回条件，区间只剩一个值return;int mid = (begin + end) / 2;//左右区间必须这么分，不然会出问题_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin;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++];}//需要把偏移量begin加上，每归并一次就拷贝一次回去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){perror("malloc fail!");}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

2. 非递归版本

如果也要使用栈实现的话，就需要两个栈，一个模仿递推的过程，一个模仿回归，就太麻烦了，其实循环就可以实现

那如果一组4个数据和一组3个数据可以进行归并嘛？也是可以的，因为归并排序并没有要求每组的数据都要相同，只要是有序就可以一起归并。

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");}int gap = 1;//gap为每组归并的数据个数while (gap < n){for (int i = 0; i < n; i += 2 * gap)//i代表每组归并的起始位置{int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}			while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}printf("\n");gap *= 2;}free(tmp);tmp = NULL;
}

我打印了一下数组区间，发现越界了

通过上图可以看出，越界可以分为两种情况

1. begin2越界了，后面就没有进行的必要的
2. end2越界了，调整end2的位置即可

if (begin2 > len - 1)//begin2已经越界,说明只有一组了没必要再排
{break;
}
if (end2 > len - 1)//end2越界了进行修正即可
{end2 = len - 1;
}

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}// gap每组归并数据的数据个数int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap)//i代表每组归并的起始位置{// [begin1, end1][begin2, end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);// 第二组都越界不存在，这一组就不需要归并if (begin2 >= n)break;// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并if (end2 >= n)end2 = n - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2])//注意等号这样才会稳定{tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}	}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}//printf("\n");gap *= 2;}free(tmp);tmp = NULL;
}

八、 计数排序

第一步：统计每个值出现的次数
第二步：排序

那如果我的数据是{100, 104, 109, 109, 102}，那count数组是不是就要开辟109个空间呢，那就太浪费空间了，所以我们要相对映射，按范围开空间，那么就用最大的值减最小的值。当我们要返回时，下标加最小的值就可以恢复了。

void CountSort(int* a, int n)
{int min = a[0];int max = a[0];//从第一个值开始对比找极大极小值for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* count = (int*)calloc(range,sizeof(int));//calloc可以将数组里的每一个值初始化为0//计数for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}free(count);count = NULL;
}

希望这篇博客对你有帮助！！！