1.排序算法的作用

1.1列如我们在购物时

筛选价格时，排序就会帮我们按价格由低到高排序或由高到低排序

1.2玩游戏时英雄战力的排行，都得用到排序算法

所以在我们的生活中排序算法无处不在

2.常见排序算法的实现

我们所有的排序算法均为升序

2.1冒泡排序

先将大家最熟悉的冒泡排序

这个排序算法我在之前的数组初阶博客中讲到过

当 i == 0时是第一躺排序，所以每一轮内比较n-1-（比较的轮数-1）

//交换
void Swap(int* e1,int* e2)
{int tmp = *e1;*e1 = *e2;*e2 = tmp;
}//冒泡排序void BubbiSort(int* a,int n){for(int i = 0; i < n-1; i++){//标记，如果数据本来有序，就不会进入Swap函数int flag = 0;for(int j = 0; j < n-1-i; j++){if(a[j] > a[j+1]){Swap(&a[j],&a[j+1]);flag = 1;}}if (flag == 1)break;}}

时间复杂度计算：

冒泡排序时间复杂度：O（N^2）
在加上我们上面的限制条件，最好情况下时间复杂度为：O（N）

2.2直接插入排序

直接插入排序在我们生活中还是很常见的
比如我们在打扑克时，在搬起一张排后，一定是将这张排插入它对应的位置
例如斗地主中，一般我们都是把王，A，2放在最左边

那我们每次摸牌都是一次插入排序
比如

我们要把这张 2 插入到这堆牌中，就要依次与后面元素比较，最后插入到王与A的中间
那我们要给一个数组排序的话
可以先把前两数看作是一组进行插入排序
然后再把前三个数看作是一组进行插入排序
……这样下去整个数组就会接近有序，例如下图

代码如下：

void InsertSort(int* a,int n)
{for (int i = 1; i < n; i++){//end作为i的前一个元素int end = i - 1;//用来保存i的位置int tmp = a[i];while (end >= 0){//排升序，如果end位置大于tmp//就把end位置的元素赋给end+1的位置if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}//程序走到这里有两种情况// 1.a[end] > tmp 就把tmp放在end的后面（a[end+1]）// 2.tmp < a[end] tmp一直小与a[end],end减到 -1 ，//说明此时的tmp最小，就把他放在对头 a[end+1] 的位置a[end + 1] = tmp;}
}

时间复杂度计算：

直接插入排序时间复杂度：O（N^2）
如果数据是有序的话，最好情况下时间复杂度为：O（N）

那如果是数据接近有序，我们插入排序的时间复杂度是多少呢？
这就引出了接下来的希尔排序

2.3选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

排序思想：每次选出一个最小的数

void SelectSort(int* a, int n)
{for (int i = 0; i < n; i++){//默认i位置为最小的数，依次与后面的数相比较int mini = i;for (int j = i + 1; j < n; j++){if (a[mini] > a[j]){mini = j;}}Swap(&a[i], &a[mini]);}	
}

时间复杂度计算：

所以选择排序时间复杂度为:O（N^2）
选择排序时间复杂度最好也是：O（N^2）

前面的排序时间复杂度都为O（N^2），排序思想也是比较简单的
接下来我们将几个效率高，比较复杂的排序算法

2.4希尔排序⭐

希尔排序就相当于插入排序的升级版
它的思想是先使数组逐渐变的有序，最后使用插入排序使数组变的有序

插入排序
插入排序是每次与前面一个数字比较，使数组有序如果当前数小于前面的数字，就继续再向前比较，如果大于或等于前面的数字就不用比较了
插入排序是先比较前两个然后比较前三，前四个······

那希尔排序又有哪些不同呢？
它是把每次数字的跳跃的间隔扩大
比如：我们让他间隔着三个数来比较，使数组有序

//gap为3的 插入排序
void Sort(int* a, int n)
{int gap = 3;//gap为3，我们就有三组数据，每次跳过3个数据//我们用下标来表示，最后一个数的下标是 7//第一组  0 3 6//第二组  1 4 7//第三组  2 5 for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){//end作为要被比较的数的下标int end = i;//tmp要向前比较的元素int tmp = a[i + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

上面代码我们可以把两个for循环写到一起，代码如下：

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

这样排序后，数组就接近有序了
那我们把gap设置为4，5呢？

仔细观察我们可以发现：
gap越大，跳的越快，越不接近有序
gap越小，跳的越慢，越接近有序

这就引出了我们的希尔排序
我们让gap == 数组元素个数，每次给gap /= 2
任何一个数除2最后都会等于1，当我们gap为1的时候就相当于是插入排序了，只是排序这个数组已经接近有序了。 当数组接近有序时使用插入排序来排序，效率就会很高
希尔排序代码如下：

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

大家发现代码中我们对gap的调整有两种方法
其实gap = gap / 3 + 1；最终也可以使gap等于1。

时间复杂度计算：

如果gap == 2，那么数组的排序次数为 (n/2需要调整的次数) + (n/4需要调整的次数) + (n/8)需要调整的次数)……;
这里每次调整都会对之后的排序进行优化，经计算大约时间复杂度为n^1.3
平均时间复杂度：O(N^{1.3}次方)
时间复杂度：O(NlogN)

2.5堆排序⭐

想要学会堆排序要先去学一下二叉树哦！
否则你根本不知道它的向下调整排序在干什么！
这里有我之前讲的关于堆排序的方法及时间复杂度

2.6快速排序⭐（排序界大哥）

快速排序的基本思想为，以一个数为参照，一趟排序下来，确定这个数在数组中的位置，并且这个数确定之后，它左边的所有数一定小于等于它，它右边的所有数一定大于等于它。

2.6.1hoare版本

先把gif图给大家看，参照着这个图来理解我下面的这段话

首先大家要知道快速排序是hoare大佬发明的，所以先讲hoare大佬的方法。
他是以左边第一个数为参照数，再从右边开始向左找比参照数小的数，再从左开始开始向右找比参照数大的数，然后交换这两个数，直到左边的下标 >= 右边的下标。
此时左右下标的相交点就是参照数应该在的位置，把相交点位置的数与参照位置的数相交换，然后把数组再分成两部分。
左边是开始位置到（相交点位置-1）
右边是（相交点位置+1）到 尾部
这样下去数组最终就会有序。
看到上面的思想，我们就知道了，快排用递归的方法写是比较简单的。

我们先写出它的一趟排序

void QuickSort1(int* a, int left, int right)
{//让参照的数为左边的数int keyi = left;int begin = left;int end = right;while (left < right){//从右向左找小while (a[right] >= a[keyi] && left < right)right--;//从左向右找大while (a[left] <= a[keyi] && left < right)left++;Swap(&a[left], &a[right]);}//到这里a[left],a[right]一定是指向同一个数的//所以a[keyi]与谁交换都可以Swap(&a[keyi], &a[left]);keyi = left;}

先来讲一下上段代码中我们可能出现的问题：

问题1.

上图中的两个红框，我们可能会丢掉这里的判断。
假设数组是有序的，可能你会出现这样的情况

问题2.

这里的等于号也是我们容易忘记写的。
有的同学可能会说，把begin=left+1，就可以了。
那请看一下，下面这种情况

这样还是会死循环，所以我们必须要加上 = 号。
hoare的排序算法代码完整版如下：

void QuickSort1(int* a, int left, int right)
{if (left >= right)return;//让参照的数为左边的数int keyi = left;int begin = left;int end = right;while (left < right){//从右向左找小while (a[right] >= a[keyi] && left < right)right--;//从左向右找大while (a[left] <= a[keyi] && left < right)left++;Swap(&a[left], &a[right]);}//到这里a[left],a[right]一定是指向同一个数的//所以a[keyi]与谁交换都可以Swap(&a[keyi], &a[left]);keyi = left;QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);
}

2.6.2挖坑法

挖坑法实际是在hoare大佬的版本上改动了一点
它是把之前的保存参照下标，改成了保存参照数本身
然后设置一个坑位，坑位最初为参照数的下标
当右边的数小于参照数，就把右边的数放到上一个坑位，坑位放到小于参照数的这个位置
当左边的数大于参照数，就把左边的数放到上一个坑位，坑位放到大于参照数的这个位置
观察整个数组其实挖坑法其实是把小于key的放在数组左边，大于key的放在右边，最后把key放在最后的坑位

挖坑法代码如下：

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int hole = left;int begin = left, end = right;while (left < right){while (a[right] >= key && left < right)right--;a[hole] = a[right];hole = right;while (a[left] <= key && left < right)left++;a[hole] = a[left];hole = left;}a[hole] = key;QuickSort2(a, begin, hole - 1);QuickSort2(a, hole + 1, end);
}

2.6.3前后指针版本

前后指针法，prev指向第一个元素，cur指向prev的下一个元素，keyi记录第一个元素下标
cur一直向后走，直到它超出数组的长度就停下
如果下标为cur的数 大于 下标为keyi的数，cur就继续向后走
如果下标为cur的数 小于 下标为keyi的数，先++prev ，再与下标为的数cur交换。

void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int prev = left;int cur = left + 1;int begin = left, end = right;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[keyi]);QuickSort3(a, begin, prev - 1);QuickSort3(a, prev + 1, end);
}

快速排序的时间复杂度：

如果每次都可以找到正中间的那个数，确定它的位置后，接下来的递归图如下

如果每次都是最好的情况（参照数的位置在中间），我们只需要递归logn次（因为层数越靠后，每趟确定的元素个数越多，呈指数被增长），每次访问的元素给数大约都可以看作n，所以

那如果遇到有序的数组用快排思想来排序呢？

这样我们的时间复杂度，就变成了O（N^2）

时间复杂度为：N*logN
最坏情况为:O（N^2）
那我们的标题都说了，快速排序是最强的排序，如果遇到最坏情况（数组是有序的）该怎么办呢？

解决数组有序的方法

方法一：
用随机函数在数组中随机抽取一个数，与左边第一个元素交换
代码如下：

srand((unsigned int)time(NULL));
int randi = left + rand() % (right - left);
Swap(&a[randi],&a[left]);

方法二：
三数取中法（用左边数，中间数，有边数比大小，谁在中间，谁就与左边的数交换）
代码如下：

//三数取中
int GetMid(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else{//a[left] > a[mid]if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}int mid = GetMid(a, left, right);
if (left != mid)Swap(&a[mid], &a[left]);

2.6.4快排非递归

快排非递归的思想是借助栈来帮助排序。
每次在栈中保存右边与左边的下标这里先保存右边再保存左边，出栈时接收返回值就先用begin接收右边下标，再用end接收左边下标
把begin和end下标传给之前写好的QuickSqrt的任意一个版本，返回被调整好后的数的下标
然后再判断是否入栈，具体逻辑看代码
再写一个循环判断栈是否为空，如果栈区为空就说明排序完成。

完整代码如下，栈的代码在我之前的文章中讲过，这里就不提了。

void Swap(int* e1, int* e2)
{int tmp = *e1;*e1 = *e2;*e2 = tmp;
}//三数取中
int GetMid(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else{//a[left] > a[mid]if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}int QuickSort(int* a, int left, int right)
{//三数取中int mid = GetMid(a, left, right);if (left != mid)Swap(&a[mid], &a[left]);int keyi = left;int prev = left;int cur = left + 1;int begin = left, end = right;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[keyi]);return prev;
}void QuickSortNonR(int* a, int left, int right)
{Stack st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = QuickSort(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (keyi - 1 > begin){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}int main()
{int arr[] = { 9,12,5,8,21,7,8,6 };int sz = sizeof(arr) / sizeof(arr[0]);QuickSortNonR(arr, 0, sz - 1);return 0;
}

2.7归并排序

归并排序的思想是，先使数组的左边与右边有序，再把左右两边的数排成有序数组

2.7.1递归思想

归并排序的思路有点类似二叉树的后序遍历
我们先要递归把数组分成两部分，分到左右两边就剩一个数的时候就停下来，然后左右两边进行归并，谁大谁放在前面。
因为是要归并整个数组，如果我们直接把大的数放在前面，会覆盖小的值，我们应该再创建一个数组，用来存放归并后的有序数组，然后再拷贝回原来的数组。

void _MergeSort(int* a,int left,int right, int* tmp)
{if (left >= right)return;int mid = (left + right) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int j = left;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 + left, tmp + left, sizeof(int) * (right - left + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}int main()
{int arr[] = { 9,12,5,8,21,7,8,6 };int sz = sizeof(arr) / sizeof(arr[0]);MergeSort(arr, sz);return 0;
}

2.7.2非递归

通过观察我们之前画的图，可以发现，最下层的每组都一个元素，往上一层每组元素就是当前层每一组元素的个乘2，相当于我们直接先去调整最下层的排序，然后依次向上，直到整个数组。

void MergeSortNonR(int* a,int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\\n");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//begin1不可能越界，因为有循环条件限制//end1只要越界，begin2就一定越界，当这两个有越界时就不用继续排序了直接break//如果begin2没有越界end2越界就还可以继续排序，把end2的下改成数组的最后一个数的下标if (end1 >= n || begin2 >= n){break;}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));}gap *= 2;}free(tmp);}int main()
{int arr[] = { 9,12,5,8,21,7,8,6 };int sz = sizeof(arr) / sizeof(arr[0]);MergeSortNonR(arr, sz);return 0;
}

时间复杂度计算：

数组每次除 2 直到每组为一个数时停止，所以我们分组需要分logN（默认以2为底）次，所以
时间复杂度为：O（NlogN）次
最坏和最好情况时间复杂度都为：O（NlogN）次
空间复杂度为：O(N)

计数排序

基数排序就是再新建一个数组，这个数组用来记录需要排序的数组中每个元素出现的个数。
没出现过的元素就是 0 次
如下图：

只需要打印数组中不为0的元素的下标就可以了。
但这样有一个很明显的缺陷，如果我们数组中最小元素很大怎么办呢？
比如数组中最小元素是 1000，那我们前面就要浪费1000个空间吗？
相信聪明的你一定想到了解决办法！

我们可以用新数组中第一个元素来代表最小值。
新建数组的元素个数就是要排序数组中的最大值-最小值

所以计数排序适合待排序数据是集中的一些数，否则会浪费大量空间。
计数排序代码如下：

void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}int range = max - min + 1;int* countA = (int*)calloc(range,sizeof(int));for (int i = 0; i < n; i++){countA[a[i] - min]++;}int j = 0;for (int i = 0; i < range; i++){while (countA[i]--)a[j++] = i + min;}free(countA);
}

再数据集中的情况下：
时间复杂度为：O（N）
空间复杂度为；O（N）

3.排序算法复杂度及稳定性总结

复杂度我们前面都讲到了，这里我们说一下稳定性是什么。
假设我们有下面这样一组数：
相同元素顺序不发生改变的视为稳定。
这里我讲以一下选择排序，我们每次选最小的数放左边。如果最小的数与左边的数相等可以不交换，这样大家可能会认为选择排序是稳定的。但事实上不是。如下图：

数组中最小数为1与左边元素交换，这样前面的8就与后面8的前后顺序交换了，所以说选择排序不稳定。