【算法速查】一篇文章带你快速入门八大排序(上）

在这里插入图片描述

君兮_的个人主页

即使走的再远，也勿忘启程时的初心

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，首先在这里祝大家中秋国庆双节同乐！！今天用一篇文章为大家把八大排序算法都过一遍，当然由于篇幅的原因不是每一种算法都详解，这篇文章更多是作为让初学者有一个初步的了解以及学过的人某个排序算法忘了的话的快速回忆，后续我也会把每种算法的重点以及难点挑出来单独为大家讲解的

好了废话不多说，开始我们今天的学习吧！！
八大排序算法
- 什么是排序？
- - 常见的排序算法
- 插入排序
- - 直接插入排序
  - 希尔排序
- 选择排序
- - 直接选择排序
  - 堆排序
  - - 向下调整
    - 建大堆
    - 堆排
- 总结

什么是排序？

*排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
*稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
稳定性简单来说，就是在排序后是否改变原数据中相等元素的顺序，改变少的或者不改变的即为稳定性好的排序
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

常见的排序算法

排序在日常生活中的应用的重要性无需多说，小到每一次成绩的排名大到国家总GDP值排名处处是排序，目前，常见的排序有八种，我们接下来都会逐一介绍，现在通过一个图来简单认识一下这几种排序

插入排序

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

直接插入排序

直接插入排序基本动图如下：
以此图的升序为例，插入排序的思想是：
*1.假设前n-1项是有序的，比较第n项与n-1项，当第n项元素比第n-1项大时，无需改变位置，当第n项元素比第n-1项小时，交换两个元素的位置，继续与前面的有序数据进行比较，直到遇到比第n项元素小的元素或者排到已经需要排序的数据的头，停止排序，此时视为完成一趟插入排序
2.继续排序，此时前n项数据是有序的，第n+1项数据重复上述的步骤，多趟插入，直到到所需排序数据的结尾
代码实现

// 插入排序
void InsertSort(int* a, int n)  //a为所需排序的数组，n为该数组数据的个数
{for (int i = 0; i < n - 1; i++){//从0开始，多趟插入int end = i;//要插入的元素int tmp = a[end + 1];//单趟插入排序while (end >= 0){//要插入的元素比此时有序数组的最后一个元素小if (tmp < a[end]){//交换 a[end + 1] = a[end];//与前一个元素再比较end--;}//插入的元素比最后一个元素大 该趟插入排序结束elsebreak;}//最后一个元素就是我们要插入的元素a[end + 1] = tmp;}}

此时可能会有一些初学者和我才开始学插入排序时一样有些疑惑，当tmp<a[end]时，a[end+1]=a[end],a[end]=a[end],数据中不就有个元素被覆盖了吗？不应该把tmp的值赋给此时的a[end]吗？
这一步其实可有可无，注意看，如果下一次tmp还小于a[end]，此时a[end+1]也就是上一轮的a[end]就会被赋值，当tmp大于a[end]时，循环结束a[end+1]也会被赋值，因此无论是哪种情况这段代码都是进行了相应的处理的，因此是否把tmp赋值给a[end]也就无关紧要了。
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap(gap>=1)，把待排序文件中所有记录分成几个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达gap=1时，所有记录再在统一组内排好序
简单来说，就是对所需排序的数据先进行几次预排序，使该组数据基本满足小的元素在前，大的元素在后（也就是越接近有序），最后再对整体进行一次直接插入排序
希尔排序代码如下

// 希尔排序
void ShellSort(int* a, int n) // a为待排序数组，n为数据个数
{//让gap等于n，第一次排序时gap为n/2，之后gap/=2，直到gap==1，进行最后一次希尔排序，完成对所需排序数据的排序int gap = n;while (gap>1){gap /= 2;for (int i = 0; i < n - gap; i++){//从第0个元素开始int end = i;//每个元素间隔为gapint tmp = a[end + gap];//每一趟预排序while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];//所需比较元素的间隔为gapend-=gap;}elsebreak;}a[end + gap] = tmp;}}

很多人会有这样的一个疑问，对于希尔排序的多趟排序，为什么结束的位置是n-gap，难道后面的数据就不排了吗？尤其是当开始时，gap是非常大的，后面还有很多元素仍然处于无序的状态。
这样做的目的是防止越界，同时，如果你仔细分析一下这段代码，其实看似后面还有很多元素未排序，其实都已经排好了，我们以当gap最大为n/2时为例，此时最后一个元素为a[n-gap-1] 而tmp为a[n-1]可见其实所有的元素都已经比较了。
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，我们现在通俗的认知为 O(N^1.3)
4. 稳定性：不稳定
有些初学者觉得既然直接插入排序是稳定的，那么只是比直接插入排序多了几次预排序的希尔排序也是稳定的吧，下面我来为大家举个反例
排在前面的9现在却排到了后面，现在你还觉得希尔排序是稳定的吗？由于在分组预排序时可能会让两个相同的元素分到不同的组中，造成上图这种情况，因此，希尔排序是不稳定的！

选择排序

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

直接选择排序

基本思想：
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
简单来说，就是通过遍历的方式找出该组数据中最大的元素和最小的元素，并把它们交换到该组数据的结尾和开头，再进一步找到该组数据次大的元素和次小的元素，交换到倒数第二个位置和第二个位置，直到该组数据只剩下一个元素或者没有元素。
上图以每次找最小为例，实际是找最大和最小同时进行的

// 选择排序
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end)//等于与大于时只剩下1个或0个元素，停止选择排序{//暂时让最大和最小的都指向beginint minSize = begin;int maxSize = begin;//最大最小都指向begin，从begin+1开始for (int i = begin+1; i <= end; i++){//找该组数据中最大的元素，通过maxSize保存其下标if (a[i] > a[maxSize]){maxSize = i;}//找该组数据中最小的元素，通过minSize保存其下标if (a[i] < a[minSize]){minSize = i;}			}Swap(&a[begin], &a[minSize]);//交换最小和此时的begin//修正if (maxSize == begin)maxSize = minSize;Swap(&a[end], &a[maxSize]);//交换最大和此时的endbegin++;//找次大和次小的end--;}
}

其中有个小小的细节需要注意，我们来看看出现以下情况时可能会发生的错误
发生以上的情况，我们的排序就全乱了，因此需要上面代码中的修正

//修正if (maxSize == begin)maxSize = minSize;

当我们发现最大的值就是下标为begin的值后，此时begin已经与minSize交换，我们让maxSize=minSize，找到我们被交换走的最大值。
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆
以排升序为例
1、将待排序的数据构造成一个大堆，当前堆的根节点（堆顶）就是该组数组中最大的元素；
2、将堆顶元素和最后一个元素交换，将剩下的节点重新构造成一个大堆；
3、重复步骤2，每次循环构建都能找到当前堆中的最大值，并通过交换的方式把它放到该大堆的尾部，直至所有元素全部有序
具体实现

向下调整

无论是建大堆还是进行堆排序都需要一个能够实现把大的数据向下调整的算法，那么是如何实现的呢？
基本思想

1、从根节点开始，选出左右孩子中值较大的一个
2、如果选出的孩子的值大于父亲的值，那么就交换两者的值，不大于，说明此时孩子和父亲都处于合适的位置，不再向下调整
3、将大的孩子看做新的父亲，继续向下调整，直到调整到叶子节点为止

注意：
上面的向下调整的思想的前提是——根结点的左右子树必须都为大堆。
向下调整图示
此时我们是采用的从根节点开始向下调整节点，通过图我们也能发现从根节点开始的向下建堆并不能保证把最大的元素放到堆顶，这是下面建堆部分的知识，我们下面再讲，这里我们的一次向下调整就完成了，代码实现如下


// 堆排序
void AdjustDwon(int* a, int n, int parent)
{int child = parent * 2 + 1;//到叶子节点就停止while (child < n){//选出孩子中最大的if (child + 1 < n && a[child + 1] > a[child]){child++;}//孩子比父亲大就交换，并使此时的孩子成为下一次循环的父亲if (a[parent] < a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//父亲更大，由于左右子树一定是大堆，不需要进一步朝下进行，直接退出循环else{break;}}}

建大堆

在开始我们的堆排序之前，我们得先通过向下排序的方式把我们需要排序的数据建立一个大堆
上面我们通过对向下调整的图示也看出了，从根节点开始进行向下调整建大堆存在一定的局限性，因此我们建大堆选择从倒数第一个非叶子节点开始，从后往前，将其作为父亲，依次向下调整，一直调整到根的位置

//这里n是数组元素个数，i作为下标-1，同时在由孩子找父亲时，parent=（child-1）/2 因此这里的i为(n-2)/2
for (int i = (n - 1 - 1) / 2; i >=0; i--)
{AdjustDwon(a, n, i);
}

在这里插入图片描述

我们通过从下到上向下调整可以避免出现上面那种孩子的孩子比父亲大建不了大堆的问题，但是当我们建好堆后，只能说它变得相对有序了，但是仍然会出现这样一个问题，如果判断左孩子和右孩子的位置？我们只保证了根节点的左右子树均为大堆，却没有保证不同子树间左右的大小问题，因此，我们为了最终排序的目的，还需要进行一步堆排序。

堆排

堆排序的思想：

1、建好堆之后，将堆顶的数字与最后一个数字交换(建的是大堆，堆顶一定是最大的数)
2、将最后一个数字排除，剩下的n-1个元素再向下调整成堆再循环进行第一步
3、直到最后只剩一个数时就停止排序。

为什么这样能成功堆排序呢？

首先，我们能确保的是，堆顶的数一定是最大的，因此把它交换的数排在此时的最后一位是合理的。
其次，我们交换上去的数字会向下调整到正确的位置，这样既保证了根节点的左右子树是大堆又能使每个交换上去的节点处于合适的位置。
重点是从后往前排的，我们一定能确保最后的数是交换下去的最大的，次大的依次类推就能保证我们排好的数据有序。

void HeapSort(int* a, int n)
{//建大堆for (int i = (n - 1 - 1) / 2; i >=0; i--){AdjustDwon(a, n, i);}//堆排，交换最后一个元素与堆顶元素，再把此时的堆顶元素向下调整int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}
}

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

总结

由于篇幅的原因，我们今天先介绍前四种排序算法，剩下的放到下篇继续，算法这一块光靠看代码不是那么容易理解的，因此我花了大量的时间画图分析，希望能对你有所帮助
当然，这篇文章创作的初衷是希望帮助初学者对排序算法有一个大致的了解，对已经学过的人起到在需要使用的时候快速回忆的效果，因此可能还有一部分细节不全，之后我会挑出重点单独出博客讲解
有任何的问题和对文章内容的疑惑欢迎在评论区中提出，当然也可以私信我，我会在第一时间回复的！！