排序算法上——插入，希尔，选择，堆排序

前言：

常见排序方法如下：

本篇将介绍4种排序方法，分别为插入排序，希尔排序，选择排序，堆排序，并分别举例与讲解。

一. 插入排序

1.1 含义与动图分析

插入排序的思想是在有序区间的下一个位置插入一个新的元素，之后将该新区间重新排序，依次类推逐个完成整个区间的排序。

扑克整理手牌时就运用了这一思想。

动态理解：

1.2 问题分析

问题：

有序数组插入新元素并排序较为简单，关键在于我们要排序的数组常常区间为无序，那么如何使要插入元素之前的区间有序呢？

分析：

1.假定有序区间为[0,end]，那么需要在[end+1]处插入新元素。

2.因此end的最大值应该小于n-1，否则end+1会导致数组访问越界

3.由于最初的数组为乱序，因此我们可以通过逐次增加有序区间的方式进行插入排序。

1.3 测试实现

代码示例如下：

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

时间复杂度分析：

最坏情况：数组降序排列
当我们对下标为i（0<i<n）的tmp数据进行插入时，会将其与前面i个数据比较i次，总比较次数即1+2+3+……(n-1)，为O(n2)
最好情况：数组升序排列
当我们对下标为i（0<i<n）的tmp数据进行插入时，只会与其前面一个数据比较一次，即总共(n-1)此，为O(n)

空间复杂度：O(1)

二. 希尔排序

在直接插入排序中我们发现，元素越无序，直接插入排序算法时间效率越低（因为比较次数越多）。特别是当数组为降序，我们要排升序，此时数组的相对无序程度达到了最大，时间复杂度也到了最大。

2.1 含义与图片分析

希尔排序，也称为递减增量排序算法，是插入排序的一种高效率的改进版本。它通过将待排序的序列分割成若干子序列，分别进行直接插入排序，从而达到整个序列有序的目的。希尔排序的核心在于间隔序列的选择，间隔序列通常是按某种规则递减至1的。 

 

 2.2 思路及相关结论

思路分析：

1.希尔排序的核心在于对数组进行预排序，值得注意的是，预排序只是让数组相对有序，而非达到真正的有序状态。

2.预排序的处理可以通过分组实现，假设数组元素个数为n，那么我们可以分为gap组，每组元素就要n/gap个（假设可以gap可以被n整除）

3. 其排序思路与插入排序基本相同，但是gap在每次排序之后，需要令gap逐次减小，当gap减小为1时，就相当于插入排序。

2.3 测试实现

//希尔排序时间复杂度：O（n^1.3)
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//保证最后一次gap一定为1for (int i = 0; i < n - gap; i++){int end = i;//n-gap-1int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}}
}

时间复杂度分析：

外层循环：gap每次除以2或3，O(log2n) 或者O(log3n) ，即O(logn)

内层循环：

假设⼀共有n个数据，合计gap组，则每组为n/gap（大致）个；在每组中，插⼊移动的次数最坏的情况下为 S=1 + 2 + 3 + ……+ (n/gap-1)，⼀共是gap组，因此：

总计最坏情况下移动总数为：gap ∗ S

gap取值有（以除3为例）：n/3 n/9 n/27 … 2 1

一一带入

• 当gap为n/3时，移动总数为： n
• 当gap为n/9时，移动总数为： 4n
• 最后⼀趟，数组已经已基本有序了，gap=1即直接插⼊排序，移动次数就是n
• 通过以上的分析，可以画出这样的曲线图：
• 

因此，希尔排序在最初和最后的排序的次数都为n，即前⼀阶段排序次数是逐渐上升的状态，当到达某⼀顶点时，排序次数逐渐下降⾄n，⽽该顶点的计算暂时⽆法给出具体的计算过程

• 内外循环综合来看，外层循环总共log3n次，内层循环的每次排序次数暂时无法精确计算，所以其复杂度不好计算。

希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》—严蔚敏书中给出的时间复杂度为：

 

• 总之希尔排序的时间复杂度综合来说是高于直接插入排序的，范围大概是O(n1.3)~O(n2)

• 总结：

  • 希尔排序的时间性能优于直接插入排序的原因：

在希尔排序开始时增量较大，分组较多，每组的记录数目少，n小，此时直接插入最好和最坏时间复杂度n2差距很小，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 

gap越大，分组越快，相对有序性越差

gap越小，分组越慢，相对有序性越好。 

当gap=1时，相当于插入排序。

三. 选择排序

3.1 含义与动图分析

思路：在整个数组内，每次选出最大的值和最小的值分别位于末尾和开头（升序情况，若为降序则与之相反），之后逐次缩小遍历选择空间。

动图图解：

 3.2 测试实现

void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin+	1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//mini begin//maxi endSwap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);++begin;--end;}}

注意：上述代码存在问题！！！

在定义maxi和mini时，我们都初始化为了begin处，但当begin处的数据即为最大值时，排序就存在了问题。

分析：

mini正常完成交换之后，begin处的最大值也被交换了过去，那么此时end处的交换就会失败，并不能完成正常功能，因为maxi始终位于begin处，而此时begin处的值已经变为了最小值。

 改进如下：

		//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据if (maxi == begin){maxi = mini;}

此时就可以解决最大值位于begin处的情况。

完整代码如下：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//mini begin//maxi end//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据if (maxi == begin){maxi = mini;}Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);++begin;--end;}
}

四. 堆排序

4.1 基本思路分析

由于堆具有相对有序的特性，要么为大堆，要么为小堆，其相当于完成了希尔排序的预排序工作，因此可以利用建堆之后再向上或向下调整来进行排序。

4.2 测试实现

排升序，建大堆

分析：

1.此时我们常常有一个误区，认为小堆与升序类似，应该建立小堆。

2. 然而在排序的时候，时间消耗过于庞大，因为在挪动元素时，会把堆内的序列和关系打乱，因此应该建大堆，然后利用算法进行调整。

代码示例如下：

void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

排降序，建小堆

思路于此相同，在此不做过多阐述。

代码示例如下：

void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

小结：本文主要讲解了四种排序方法，下篇将会继续讲解排序的其他方式，欢迎各位大佬前来斧正支持！！！