欢迎来到 Claffic 的博客 💞💞💞

“东风随春归，发我枝上花。”

前言： 

排序是日常生活中极其常见的一种算法，它的功能很简单，就是将数字按照升序/降序排列，最终形成一组有序的数字，不过形成有序数字的过程有多种实现方式，它们各有好坏，接下来，由我带你手撕排序算法。

目录

🥰写在前面 

💐Part1.插入排序 

1.1直接插入排序

1.1.1思想

1.1.2实现 

1.2希尔排序

1.2.1思想

1.2.2实现

🌺Part2:选择排序 

2.1选择排序

2.1.1思想

2.1.2实现

2.2堆排序

2.2.1思想

2.2.2实现 

写在前面 

排序离我们的生活很近，这是一种很重要的算法，比如：

网上购物按价格升序排序

世界500强排名 

排序是常见的，也是重要的，寻找最优的排序能做到优化，所以理解掌握排序是必要的。

下面是要讲解的常见排序：

我们默认实现排升序，一个一个来：

Part1.插入排序 

1.1直接插入排序

1.1.1思想

相信多数人是打牌的，你知道吗，在摸牌的时候，你就悄悄进行了插入排序操作：

这种排序就是新拿到的数字与已有的数字进行比较，确定合适的位置后进行插入操作。

结合动图深度理解： 

可以看到： 

• 当只有一个数字时，没有可比性，可理解为有序；

•  取下一个数字b，与前一个数字a比较，如果b小于a，则需要调整二者的位置，如果a小于b，符合升序，则不需要调整；

•  前一部分排好的数字逐渐增多，取此区间后最近的数字进行挨个比对，不是合适位置，比较过的数字就后移一位，是合适位置，就进行插入操作。

1.1.2实现 

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

特征分析：

当原数字越接近有序时，效率越高；

时间复杂度：最好：O(N)  最坏：O(N^2)；

空间复杂度：O(1)；

稳定性(是否动了相同数字的相对位置)：稳定

这个排序看起来效率并不高，希尔在快速排序的基础上进行了优化：

1.2希尔排序

1.2.1思想

本质还是插入排序，只不过希尔做了一个巧妙的处理：引入了 gap ，每隔一个gap分为一组；

先让一部分数字相对有序，再调整下一部分，直至最后有序；

1.2.2实现

// 希尔排序
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 endi = i;int tmp = a[i + gap];while (endi >= 0){if (tmp < a[endi]){a[endi + gap] = a[endi];endi -= gap;}elsebreak;a[endi + gap] = tmp;}}}
}

注意：gap是多少并没有明确规定，一般是 gap/3+1  

特征分析：

希尔排序是对直接插入排序的优化，给gap相当于进行预排序，当gap==1时数组就相当有序了，比起直接插入，会快一些；

时间复杂度：最好：O(N^1.25)~O(N^1.3) (参考《计算机程序设计技巧》--Knuth)  最坏：O(N^2)；

空间复杂度：O(1)；

稳定性：不稳定

Part2:选择排序 

2.1选择排序

2.1.1思想

这种排序方法是我们出厂自带的排序方法，试想：给你一堆乱序的数字，你会怎么排？

通常情况下，我们会从头到尾扫一遍，选出最小的放到最前面，再扫一眼，选出第二大的放到第二位。

这就是选择排序的基本思想。

动图： 

是不是挺符合认知规律的？ 

2.1.2实现

// 选择排序
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){// 初始化int mini = left;int maxi = left;// 找到较大/较小值的下标for (int i = left+1; i <= right; i++){if (a[i] < a[mini]) // 前后顺序会影响结果{mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[mini], &a[left]);// 调试过程中会有left与maxi重叠的情况，这时需要针对这种情况调整if (left == maxi)maxi = mini;Swap(&a[maxi], &a[right]);left++;right--;}
}

特征分析： 

直接选择排序思路易理解，但效率不高，不实用；

时间复杂度：最好：O(N^2)  最坏：O(N^2)；

空间复杂度：O(1)；

稳定性：不稳定 

2.2堆排序

2.2.1思想

堆排序在往期 什么是堆，如何实现？(附堆排序，TOP-K问题) 中有详解， 

先是建大堆，再是模拟删除操作，这里就不多说啦。

2.2.2实现 

//堆排序
void HeapSort(int* a, int n)
{//向下调整（效率更高）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--;}
}

特征分析：

利用堆的特性，选数快很多，效率较高

时间复杂度：最坏：O(N*logN)  最好：O(N*logN) ；

空间复杂度：O(1)；

稳定性：不稳定

总结：

这期是常见排序的前半部分，讲了两类排序：插入排序和选择排序，思想不难，多注意实现中的细节。我打算将后半部分放在下期：交换排序和归并排序。

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗