【数据结构与算法】排序算法(上)——插入排序与选择排序

---

一、常见的排序算法

常见排序算法中有四大排序算法，第一是插入排序，二是选择排序，三是交换排序，四是归并排序。本站文章针对前两个排序，这其中不才将拿出每个排序中所具有代表性的排序算法进行深入解读。

---

二、插入排序

基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

2.1、直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

代码实现：

void InsertSort(int* arr, int n) {// 外层循环，从第二个元素开始，逐步处理每个元素for (int i = 0; i < n - 1; i++) {// tmp 是当前元素的索引，初始值是 i+1，表示从第二个元素开始int tmp = i + 1;// end 是已排序部分的最后一个索引，初始值是 iint end = i;// 把当前比较的数据保护起来int num = arr[tmp];// 内层循环，寻找当前元素插入的位置while (end >= 0) {// 如果已排序部分的元素大于当前元素if (arr[end] > num) {// 已经把当前元素比较保护好，可以将已排序部分的元素向右移动arr[tmp] = arr[end];// tmp 和 end 都向左移一位tmp--;end--;}else {// 找到合适的位置，不需要继续向左移动了break;}}// 将当前元素插入到合适的位置arr[tmp] = num;}
}

时间复杂度：

• 最好的情况是：如果数组已经是有序的（或者几乎有序），只需要进行一轮比较，时间复杂度是O(n)。
• 最坏的情况是：数组是逆序的，每次都要比较所有已排序的元素，时间复杂度是O(n²)。

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

---

2.2、希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时即为直接插入排序，所有记录在统一组内排好序。

希尔排序的工作原理：

1. 初始间隔（gap）：希尔排序的关键点在于选择一个合适的“间隔”序列，也叫做增量序列。初始时，希尔排序会使用一个较大的间隔，比如n/2，然后通过逐渐缩小间隔来进行多次排序。

2. 分组插入排序：每次排序时，希尔排序将待排序的序列按间隔分成多个子序列。然后对每个子序列分别进行插入排序。例如：间隔为2时，序列的第一个元素、第三个元素、第五个元素、第七个元素、第九个元素，形成一个子序列(如下图gap=2时)。然后对这个子序列进行插入排序。接着处理间隔更小的子序列，直到间隔为1时，整个序列就是有序的。

3. 逐渐减小间隔：随着间隔的逐步减小，元素变得越来越接近排序完成，最后，当间隔为1时，希尔排序就变成了直接插入排序。

总的来说，希尔排序就是直接排序PRO MAX版本。使用希尔排序，它可以快速地把大数放在右边，小数放在左边。在快速区分大小数位置之后，就比原先的混乱顺序变得更有序，在直接插入排序中，我们知道元素集合越接近有序，直接插入排序算法的时间效率越高，我们就不断的往有序的方向靠近，最后再直接在使用直接排序就可以缩短大部分时间。如下图，我们使用gap来表示每一次比较的跨越元素个数。

代码的实现：（两种循环的实现）

void shellSort(int* arr, int n) {int gap = n / 3 + 1;while (gap > 1) {// 判断收缩gap的值，直到gap值为1时，完成插入排序//int gap = 3;//for (int j = 0; j < gap; j++) {//end要分别对gap分出的gap个数组进行排序，这样便可完成数组中每个位置的比较//for (int i = 0; i < n - 1 - gap; i += gap) { // 把间距把分开的每个tmp位置都进行插入排序for (int end = 0; end < n  - gap; end++) { //这样设置循环可以把end在数组中的每个位置都走一边 与上面两层循环相比只是逻辑不同，效率上没有变化//int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}//}//}gap = gap / 3 + 1;}
}

• 排序代码的实现得有里到外的编写，这样容易把控
• 首先编写一个正常的直接插入排序，并且把gap加上。

for (int i = 0; i < n - 1; i++) {int gap = 1;int tmp = i + gap;int end = i;int num = arr[i + gap];while (end >= 0){if (arr[end] > num) {arr[tmp] = arr[end];tmp--;end--;}else {break;}}arr[tmp] = num;
}

• 这样我们就改好了直接插入排序有gap时的写法了
• 我们开始修改gap每次跳转的范围，首先以gap=2为例，首先我们把i每次增加的个数都增加gap个。我们也优化变量

int gap = 2;
for (int i = 0; i < n - 1 - gap; i += gap) {int end = i;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;
}

• 这个时候，我们就完成了一个子序列：第一个元素、第三个元素、第五个元素、第七个元素、第九个元素的元素排序。但是，我们gap = 2时，我们是把原数组分为两个子序列。所以要对两个子序列都进行排序。这样我们就必须在外面再套一层循环来把gap分开的子序列都进行排序。(如下图中被分开为红蓝两个子序列)

int gap = 2;
for (int j = 0; j < gap; j++) {for (int i = 0; i < n - 1 - gap; i += gap) {int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}
}

• 子序列的第一个节点起始点，永远不会再第一个子序列的第二个节点的后面，所以我们可以通过套用外层循环j遍历的控制end的起始地址，则这样就可以完成多个子序列的访问。
  
• 这时候我们就可以完成所有子序列的第一次排序。但是为了完成原数组的整体排序，我们必须要让gap每完成一个排序就减少，直到gap = 1时，变为直接插入排序完成数组的排序。

int gap = 2;
while (gap > 0) {for (int j = 0; j < gap; j++) {for (int i = 0; i < n - 1 - gap; i += gap) {int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}}gap--;
}

• 这样我们就完成了一个低效版本的希尔排序

为何说是低效版本呢？因为gap的值是固定的。当数据量达到数十亿的级别之后。我们一个区区的常量2的效率与直接插入排序的效率几户一样。

这时候就有大佬研究出目前位置希尔排序gap的最好取值之二(n是数组的元素个数)：gap = n/2或gap = n/3 + 1(最快)。我们再自己手搓希尔排序时，使用gap选择哪个都可以。不才选择gap = n/3 + 1作为示范。

int gap = n;
while (gap > 1) {gap = (gap / 3) + 1;for (int j = 0; j < gap; j++) {for (int i = 0; i < n - 1 - gap; i += gap) {int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}}
}

• 在使用gap = n/3 + 1之后，每次gap缩小值都是gap/3 + 1。无论是什么数循环到一定次数后最后除三的都会变为零。当除3等于0时再加一gap就等于1，这时候就是直接插入排序。当gap == 1时，就不会再进入循环。

但此时，上面循环中i、j就只是为了控制end变量起始位置可以遍历一遍数组，end每次都是与gap位后的数值进行比较。那么我们就可以把两层循环变为一层循环

void shellSort(int* arr, int n) {int gap = n;while (gap > 1) {// 再收缩gap的值，直到gap值为1时，完成插入排序gap = gap / 3 + 1;for (int end = 0; end < n  - gap; end++) { //这样设置循环可以把end在数组中的每个位置都走一边，但效率上没有变化int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];//每次都与前gap值为比较end -= gap;}else {break;}}arr[end + gap] = tmp;}}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
   会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书籍中给出的希尔排序的时间复杂度都不固定：

《数据结构-用面相对象方法与C++描述》— 殷人昆

不才上面使用的是Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，暂时就按照：O(n^1.25)到O(1.6*n^1.25)来算，按照我们也可以粗略的归类与O(n * logⁿ)的量级，但是真实的时间复杂度是比O (n * logⁿ)大。

---

三、选择排序

基本思想：

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

3.1、直接选择排序

• 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
• 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
  

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---

3.2、堆排序

在堆的的逻辑结构中是严格遵循有序但这并不意味着整个堆的物理存储结构是有序的。堆排序的目的是对堆中的元素进行排序，通过堆这种数据结构的特性来实现元素的排序。

排序中分为升序和降序，堆排序即利用堆的思想来进行排序

• 排升序对应着建大堆
• 排降序对应着建小堆

堆排序的方法：

• 因为堆排序的逻辑与堆的删除逻辑是完全一致的，都是先把堆顶元素与最后一个元素进行交换之后向下调整。与删除不同的是，删除需要把数组中最后一个元素完全删除，排序只需要不再理会数组最后一个元素，不用真正删除元素。

排升序建大堆的原因在把堆顶元素与最后一个元素进行交换之后，堆中的中最大的值被放置在物理结构的最右边，如此循环即可完成结构的升序。降序同理

把堆中元素进行升序排序

我们使用上述大堆的例子创建有序的物理结构，物理结构：[95，70，8，21，5，3，4，6，9，1]

首先交换堆顶与最后一个元素(如下图)

在交换完成后逻辑结构上不再把95结点当作堆的结点，之后进行向下调整(如下图)

此时，物理结构为：[70，21，8，9，5，3，4，6，1，95]。这样就把最大值放置在物理结构最右边，并且忽略最后一个结点后，其他结点依旧保持着大堆结构。(与删除堆顶逻辑完全相同)

循环上述操作可得下图：

一定次数的循环后，会得到下图

观察上图可以看到此时物理结构:[8，6，3，1，5，4，9，21，70，95]，只要循环次数足够，就可以把物理结构排为升序

最终可得下图：

此时我们就完成了：堆中元素的升序排序。物理结构为：[1，3，4，5，6，8，9，21，70，95]。

3.2.1、堆排序的代码实现

void HeapSort(HPDataType* arr, int capacity, int farent) {assert(arr); // 确保传入的数组指针不为空int cp = capacity; // 存储堆的初始容量// 当堆中还有元素时进行排序while (cp != 0) {// 将堆顶元素（最大或最小元素）与当前堆的最后一个元素交换HeapSwap(arr, 0, cp - 1); // 减少堆的有效大小（去除已排序的最大元素）--cp;// 调整堆结构，确保堆的性质依然保持AdjustDown(arr, cp, farent);}
}

• 首先把堆顶元素与最后一个叶子节点的元素进行交换。
• 之后--元素个数，把已经交换完成的最大值(最小值)忽略。
• 完成后再向下调整。把交换完成后的顺序表，重新调整为大堆(小堆)。

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---

ps：剩下的两大排序真正紧张制作中，欲知后事如何，请听下回分解~~

以上就是本章所有内容。若有勘误请私信不才。万分感激💖💖 如果对大家有帮助的话，就请多多为我点赞收藏吧~~~💖💖

ps:表情包来自网络，侵删🌹