排序算法（sorting algorithm）是用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符 ASCII 码顺序或自定义规则，本篇博客详细介绍常见的八大排序算法的基本思想以及实现过程，以及对于算法效率的分析和比较，希望通过本篇博客，能够深入掌握排序算法！
目录
一、排序简介
1.1 什么是排序？
1.2 排序的目的是什么？
1.3 排序的应用场景
1.4 排序算法好坏的度量指标
1.5 排序算法的分类
二、常见排序算法的实现（以升序为例）
2.1 插入类排序—>直接插入排序
2.1.1 基本思想
2.1.2 算法步骤
2.1.3 图解算法
2.1.4 代码实现
2.1.5 测试
2.1.6 算法分析
2.1.7 优缺点
2.1.8 如何优化
2.2 插入类排序—>希尔排序（难）
2.2.1 基本思想
2.2.2 希尔排序的增量数组
2.2.3 算法步骤
2.2.4 图解算法(有横线的值认为已经有序)
2.2.5 代码实现
2.2.6 核心代码分析
2.2.7 测试
2.2.8 算法分析
2.2.9 总结
2.3 选择类排序—>简单选择排序
2.3.1基本思想
2.3.2算法步骤
2.3.3图解算法
2.3.4代码实现
2.3.5测试
2.3.6算法分析
2.4 选择类排序—>堆排序（难）
2.4.0 铺垫知识
2.4.1 大小堆介绍
2.4.2 基本思想
2.4.3 算法步骤
2.4.4 图解算法
2.4.5 代码实现
2.4.6 核心难点分析
2.4.7 测试
2.4.8 算法分析
2.5 归并类排序—>归并排序（难）
2.6 交换类排序—>冒泡排序
2.6.1基本思想
2.6.2算法步骤
2.6.3图解算法
2.6.4代码实现
2.6.5测试
2.6.6算法分析
2.6.7如何优化
2.7 交换类排序—>快速排序(难，笔试最常考)
2.8 基数排序
2.8.1基本思想
2.8.2算法步骤
2.8.3图解算法
2.8.4代码实现
2.8.5测试
2.8.6算法分析
2.8.7优缺点
三、排序算法复杂度及稳定性分析
四、选择题练习
一、排序简介
1.1 什么是排序？
所谓排序，就是使一串记录/数据，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
1.2 排序的目的是什么？
便于查找，有序的数据，查找时，直接使用二分查找。
1.3 排序的应用场景
排序有非常多的应用场景，这里简单举例。
1.4 排序算法好坏的度量指标
- 时间复杂度：排序速度(比较次数和移动次数)
- 空间复杂度：占内存辅助空间的大小
- 稳定性：A和B的关键字相等，排序后A，B的先后次序保持不变，则称这种排序算法是稳定。（相同值的先后顺序和初始状态下的先后顺序一致， 则认为是稳定的）
判断稳定性的小技巧：看是否存在跳跃交换，若存在跳跃交换，则不稳定，反之稳定。
1.5 排序算法的分类
根据在排序过程中待排序的记录是否全部存放在内存中，分为内部排序和外部排序。若待排序记录都在内存中，称为内部排序， 若待排序记录一部分在内存，一部分在外存，则称为外部排序。 注意：外部排序时，要将数据分批调入内存中来排序，中间结果还要几时放入外存，显然外部 排序要复杂很多。本篇博客只介绍常见的内部排序算法，主要有：直接插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序。用一张表概括如下：
术语解释：
- n：数据规模，表示待排序的数据量大小。
- k：“桶” 的个数，在某些特定的排序算法中（如基数排序、桶排序等），表示分割成的独立的排序区间或类别的数量。
- 内部排序：所有排序操作都在内存中完成，不需要额外的磁盘或其他存储设备的辅助。这适用于数据量小到足以完全加载到内存中的情况。
- 外部排序：当数据量过大，不可能全部加载到内存中时使用。外部排序通常涉及到数据的分区处理，部分数据被暂时存储在外部磁盘等存储设备上。
- 稳定：如果 A 原本在 B 前面，而 A=B，排序之后 A 仍然在 B 的前面。
- 不稳定：如果 A 原本在 B 的前面，而 A=B，排序之后 A 可能会出现在 B 的后面。
- 时间复杂度：定性描述一个算法执行所耗费的时间。
- 空间复杂度：定性描述一个算法执行所需内存的大小。
十种常见排序算法按照算法的思想可以分类两大类别：比较类排序和非比较类排序。
常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn 次，所以时间复杂度平均 O(nlogn)。
比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。而计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
二、常见排序算法的实现（以升序为例）
比较类排序算法
2.1 插入类排序—>直接插入排序
2.1.1 基本思想
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。
2.1.2 算法步骤
插入的规则如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于将要插入的元素，将该元素移到下一位置；
- 重复步骤 3，直到找到已排序的元素小于或者等于将要插入的元素的位置，则停下来；
- 将该待插入元素元素插入到该位置的后面；
- 重复步骤 2~5，直到将所有元素插入完毕。
2.1.3 图解算法
下面这张图生动的描述了每个元素的插入过程。
2.1.4 代码实现
//直接插入排序
void Insert_Sort(int arr[], int len)
{
//for(int i=0; i<len-1; i++)//控制趟数
for (int i = 1; i < len; i++)//控制趟数
{
int tmp = arr[i]; //保存待插入的元素，防止移动元素发生元素覆盖
int j; //*j申请在外面，要不跳出内层for循环，j失效了
for (j = i - 1; j >= 0; j--)//找到这一趟已排序好的序列中的合适的插入位置
{
if (arr[j] > tmp)
{
arr[j + 1] = arr[j];
}
else //arr[j] <= tmp
{
break; //arr[j+1] = tmp; //找到一个小于或者等于tmp的值
}
}
arr[j + 1] = tmp; //找到位置，插入元素
}
}2.1.5 测试
//打印数组元素
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 12,83,78,91,57,91,72,40,91,79,5,70,12,97,49,1,75,9,71,9,24,73,21 };
int len = sizeof(arr) / sizeof(arr[0]);
//打印排序之前数组元素顺序
Show(arr, len);
Insert_Sort(arr, len);
//打印排序之后数组元素顺序
Show(arr, len);
return 0;
}
2.1.6 算法分析
- 时间复杂度：O(N^2) ，双层for循环；
- 空间复杂度：O(1) ；
- 稳定性：由于他只要找到小于等于插入的元素的位置便停下来，未发生跳跃交换，所以它是一种稳定的排序算法；
特点：元素较少或者元素越接近有序，直接插入排序算法的时间复杂度越低，反过来，元素越接近逆序，时间复杂度越高。因为元素越有序，则移动元素的次数便越少，因此时间复杂度便越低。
2.1.7 优缺点
- 优点：
1.如果n较小，那么n^2也不会太大（当数据量较小时，可以直接使用直接插入法）
2.较为稳定- 缺点
时间复杂度过高（n^2）
2.1.8 如何优化
通过上面的分析，我们可以知道：如果数据量特别少，或者数据量较为有序，直接插入法效率极高，关键点就是如何让待排序列数量降低，又如何让它变得接近有序呢？下面的希尔排序就是直接插入法的优化
2.2 插入类排序—>希尔排序（难）
希尔排序(也称缩小增量排序)是D.L.Shell于1959年剔除的一种排序算法，在这之前人们认为排序算 法的时间复杂度基本都是O(n2 )，而希尔排序是突破这个时间复杂度的第一批算法之一，希尔排序是对于 直接插入排序的优化。
希尔排序的算法思想的出发点：
- 直接插入排序在基本有序时，只需要少量的插入操作，就可以完成整个数据的有序，效率很高；
- 直接插入排序在数据个数较少时，效率很高；
可问题在于，这两个条件本身过于苛刻，现实中数据集能保证基本有序都属于特殊情况了。不过不 需要急，有条件当然最好，没有条件，则创造条件就好了，于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以提高效率。针对上述两个出发点，应该如何针对性的解决呢？来看看希尔怎么分析的。
2.2.1 基本思想
1. 如何让待排序数据变少？
对数据进行分组。分割成若干个子序列，再对这些个子序列分别进行直接插入排序；
2.如何让数据变得基本有序？
当经过上面的分组然后进行直接插入排序后（预排序步骤），整个序列就会变得基本有序，再对全体数据进行一次直接插入排 序，这时就可以保证全体数据完全有序了。
怎么样进行分组呢？
对比上面的两种分割方式，可以知道，利用分割方式2进行直接插入排序，会让原数据变得更加有序:大的数据主要分布在后面，小的数据分布在前面。并且每选择一次增量排序，整个数据就会变得越来越有序，因此，应采用方式2. 对插入排序的优化，让元素更快速地交换到最终位置.
因此，它的思想如下：
对于n个待排序的数据，取一个小于n的整数gap(gap被称为步长或增量)将待排序元素分成若干个组子序列，所有距离为gap的倍数的数据放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，整个数据就会变得基本有序，然后最后一次，取gap=1时，进行一次插入排序，整个数据就是有序的。
2.2.2 希尔排序的增量数组
希尔排序也叫最小增量排序，有一个最重要的标志——增量数组,希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。那么这里“增量”的选取就非常关键了。 只不过迄今为止还没有人找到一种最好的增量序列，目前还是一个世界难题，但是增量序列的最后 一个增量值必须等于1才能。
增量数组一般取 [5,3,1]，尽可能保证增量数组里面的值互素，并且最后一个的增量一定是1 （只有最后以增量为1排序一次，才能保证数据全部有序）
2.2.3 算法步骤
- 选择增量数组，分组实现直接插入，每组元素间隙称为 gap
- 每轮排序后 gap 逐渐变小，直至 gap 为 1 完成排序，（增量元素个数k, 决定对数据进行 k 趟排序；
2.2.4 图解算法(有横线的值认为已经有序)
2.2.5 代码实现
//这一趟排序 对arr数组中的数据来说 以gap为增量进行分组
void Shell(int arr[], int len, int gap)
{
//假设gap=5，则认为前5个值已经有序，则让i直接指向第一个组的第二个值下标
for (int i = gap; i < len; i++)//控制趟数 //********//
{
int tmp = arr[i];
int j; //*j申请在外面，要不跳出内层for循环，j失效了
//这里修改了，找到这一趟已排序好的序列中的合适的插入位置
for (j = i - gap; j >= 0; j -= gap)
{
if (arr[j] > tmp)
{
arr[j + gap] = arr[j]; //这里修改了
}
else
{
break;
}
}
arr[j + gap] = tmp; //这里修改了
}
}
//希尔排序 时间复杂度O(1.5) 空间复杂度O(1)
void Shell_Sort(int arr[], int len)
{
int gap[] = { 5, 3 ,1 }; //缩小增量数组
int gap_len = sizeof(gap) / sizeof(gap[0]);
for (int i = 0; i < gap_len; i++)
{
Shell(arr, len, gap[i]);
}
}2.2.6 核心代码分析
我们发现分割后的多个子序列，分别需要进行直接插入排序，但是我们代码中只用了一个for循环就 搞定了，核心要点在于并不是一个子序列处理完后才处理下一个子序列，而是所有子序列同步进行，如下图所示：(将所有组看成一个整体，每次处理每个组的一部分， 这样可以只需要一个双重for循环)
2.2.7 测试
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 12,83,78,91,57,91,72,40,91,79,5,70,12,97,49,1,75,9,71,9,24,73,21 };
int len = sizeof(arr) / sizeof(arr[0]);
Show(arr, len);
Shell_Sort(arr, len);
Show(arr, len);
return 0;
}
2.2.8 算法分析
- 时间复杂度：希尔排序的时间复杂度比较特殊，受限于“增量”的选取，时间复杂度大约为O(n^1.5 )，也可以认为在 O(n^1.3 ~ n^1.7 )之间。
- 空间复杂度：O(1) ；
- 稳定性：另外由于发生跳跃式的移动，所以希尔排序并不是一种稳定的排序算法。
2.2.9 总结
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
每组数据是在前一轮排序后重新分组的，也就是说第二轮排序是在第一轮排序的基础之上，那么组内元素就有第一轮排序的前提，也就是局部有序的，这充分了利用了插入排序对于局部有序数据排序的高效性。后序轮次以此类推，直到 gap 缩小为 1，也就是只分一组，对所有元素进行最后一轮排序。
2.3 选择类排序—>简单选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n2) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
2.3.1基本思想
每一趟从待排序序列中找到最小值，和待排序序列第一个值进行交换，从而让待排序序列个数-1，重复执行，直到数据完全有序。
2.3.2算法步骤
- 首先在待排序序列中找到最小元素，存放到已排序序列的第一个位置
- 再从剩余待排序元素中继续寻找最小元素，然后放到已排序序列的第一个位置。
- 重复第 2 步，直到所有元素均排序完毕。
注意：为防止数据交换时发生覆盖，跑完一趟，需要用两个变量记录的是待排序序列最小值和待排序序列第一个值的下标！！！
2.3.3图解算法
2.3.4代码实现
//选择排序
void Select_Sort(int *arr, int len)
{
for(int i=0; i<len-1; i++)//控制循环的趟数 len-1趟
{
int min = i;//让min 保存 这一趟循环中"待排序序列"的第一个值的下标
for(int j=i+1; j<len; j++)//找到这一趟排序中，待排序序列的最小值的下标，用min保存
{
if(arr[j] < arr[min])//如果发现了比min指向的值还要小的值，则min修改指向
{
min = j;
}
}
//此时，里面这一层for循环跑完，代表着min正保存着待排序序列的最小值的下标
// 而此时待排序序列的第一个值的下标，由变量i保存
if(min != i)//如果min==i， 代表着待排序序列最小值就是待排序序列第一个值
{
int tmp = arr[min];
arr[min] = arr[i];
arr[i] = tmp;
}
}
}
2.3.5测试
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 12,83,78,91,57,91,72,40,91,79,5,70,12,97,49,1,75,9,71,9,24,73,21 };
int len = sizeof(arr) / sizeof(arr[0]);
Show(arr, len);
Select_Sort(arr, len);
Show(arr, len);
}
2.3.6算法分析
- 时间复杂度：O(n^2 )
- 空间复杂度：O(1) ；
- 稳定性：发生跳跃移动交换，属于不稳定算法
如下图所示，元素 nums[ i ] 有可能被交换至与其相等的元素的右边，导致两者的相对顺序发生改变。
2.4 选择类排序—>堆排序（难）
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。我们可以利用“建堆操作”和“元素出堆操作”实现堆排序。输入数组并建立大顶堆，此时最大元素位于堆顶。不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。为什么堆排序属于选择类排序的一种呢？
因为堆排序在一定程度上有着与选择排序类似的思想，也是每次在数组中选择最大的元素的值然后交换到数组的最后一位，最终实现有序，但是传统的选择排序在选择最大值的过程中采用的是遍历比较，每次选择最大值都需要遍历未排序区域，但是，想要选择最大值，堆数据结构是一个非常合适的解决方法，我们将数据构建为堆数据结构，每次选择最大值只需要拿到堆顶元素即可，然后对堆做一次下潜操作，继续构建堆结构。
2.4.0 铺垫知识
- 二叉树：每个节点最多只能有两棵子树，且有左右之分。
- 完全二叉树：可以少节点，并且只能在最后一层缺少节点，不能出现右边存在节点，而左边缺少节点的情况，因为节点是从左到右的排列的，则此二叉树成为完全二叉树。
- 满二叉树： 除了叶子节点以外，其余每个节点都有两个子节点。每一层完全放满，满足等比数列，公比为2。特殊的完全二叉树
- 树高 ：树的层数。
- 叶子节点：度为0的节点，也就是最外层的节点。
- 非叶子节点：度不为0的节点。
2.4.1 大小堆介绍
堆是具有下列性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
很明显，我们可以发现它们都是二叉树，再具体点都是完全二叉树。左图中根结点是所有元素中最大的，右图的根结点是所有元素中最小的。再细看，发现左图每个结点都比它的左右孩子要大，右图每 个结点都比它的左右孩子要小。这就是要讲的堆结构。
2.4.2 基本思想
将待排序序列构造一个完全二叉树，然后调整成大顶堆(升序)，此时堆顶根结点的值可以保证为整个序列中的最大值，接下来，将其和堆数组的末尾元素进行交换，此时末尾元素就 是最大值，然后将剩余的n-1个序列重新调整成大顶堆，这样就会得到n-1个数据元素中的最大值。反复上述操作，直到这个大顶堆只剩下一个结点时，则可以得到一个有序序列了。
- 升序使用大顶堆
- 降序使用小顶堆
2.4.3 算法步骤
- 先将数组中的值构造成一一个完全二叉树(臆想，数据还在数组中)；
- 将第一步臆想出来的完全二叉树调整为大顶堆，调整规则为：从最后一个非叶子结点开始，从右向左，从下向上进行调整；
- 因为大顶堆的特点:根节点是最大值，将根结点的值和当前尾结点进行交换，然后让尾结点剔除出去，后面进行调整时，这个尾结点不参与后续调整；
- 再次对完全二叉树进行调整，因为只有根节点发生了改变（根节点和尾节点进行交换导致不再是大顶堆，其它的小的大顶堆没有发生变化）,则这时调整只需要调整最外层的框（以根节点构成的最大的二叉树）即可；
- 反复执行3, 4操作，直到完全二叉树只剩下一个结点的时候,停止，不再继续!
2.4.4 图解算法
第一步：臆想成完全二叉树，没有代码。
第二步：第一次调整为大顶堆
调整过程描述如下：
以第1个非叶子节点8为根节点构成的二叉树（红色框）开始，申请一个临时变量保存根节点8，将此根节点的值8与左右孩子的较大值12比较，8小于12，因此12往上移，出现空白格子（12节点的位置），开始调整以空白格子12为根节点的二叉树继续调整，从图上可知：12没有左右孩子（触底了），因此它不需要调整，直接将8挪下来放到原来12的位置。红色框调整完毕；
接下来调整绿色框，以6为根节点构成的二叉树（绿色框）开始，申请一个临时变量保存根节点6（出现空白格子），将此根节点的值6与左右孩子的较大值21比较，6小于21，因此21往上移，出现空白格子（21节点的位置），开始调整以空白格子21为根节点的二叉树继续调整，从图上可知：21没有左右孩子（触底了），因此它不需要调整，直接将6挪下来放到原来21的位置。绿色框调整完毕；
接下来调整蓝色框，以15为根节点构成的二叉树（蓝色框）开始，申请一个临时变量保存根节点15（出现空白格子），将此根节点的值15与左右孩子的较大值21比较，15小于21，因此21往上移，出现空白格子（21节点的位置），开始调整以空白格子21为根节点的二叉树继续调整，从图上可知：21的左右孩子为11和6，二者的较大者为11，21大于16，因此，直接将15放到21的位置即可，蓝色框调整完毕。
第三步：将根结点的值和当前尾结点进行交换，然后让尾结点剔除出去，后面进行调整时，这个尾结点不参与后续调整，图上展示就是断开那条线；
第四步：再次对完全二叉树进行调整，则这时调整只需要调整最外层的框（以根节点构成的最大的二叉树）即可；
第五步： 反复执行第3和第4步操作，直到完全二叉树只剩下一个结点的时候,停止，不再继续!
此时，数组中的元素已经完全有序！
总结：
第一次刚进来的时候，对完全二叉树进行调整为大顶堆，需要从内到外调整一遍
而对于接下里头尾节点交换之后的调整就只需要调整一下最外层的框即可！
2.4.5 代码实现
堆排序的单次调整 (通过start和end来限定大顶堆中要处理的框框) Heap_Adjust是O(logn)
void Heap_Adjust(int *arr, int len, int start, int end)
{
int tmp = arr[start]; //将start这个下标的值 拷贝到tmp
难点4: 如何控制是否触底？i=start*2+1： //**i指向空白格子的左孩子
for(int i=start*2+1; i<=end; i=i*2+1)
{
//判断，当前空白格子是否存在右孩子，如果右孩子存在且大于左孩子，则让i指向较大孩子
if(i+1<=end && arr[i+1] > arr[i])
{
i++; //目的是让i一直指向左右孩子中的较大值
}
//这个if执行结束，i肯定指向空白格子的较大孩子
if(arr[i] > tmp)//较大孩子值还大于父节点，向上挪动
{
arr[start] = arr[i];//将较大孩子值挪动到当前空白格子，则出现新的空白格子
难点5：start要指向新的空白格子start一开始指向空白格子，当较大孩子向上挪动，出现了新的空白格子，
这时start随之更新一下
start = i;
}
else
{
arr[start] = tmp; 难点6：退出情况2：左右孩子较大值小于tmp
break;
}
}
难点6：退出情况1：触底了，tmp的值，也需要放回来，放回到arr[start]
arr[start] = tmp;
}
//堆排序 升序（大顶堆） 降序（小顶堆）
//时间复杂度O(nlogn) 空间复杂度O(1) 稳定性：不稳定
void Heap_Sort(int *arr, int len)
{
//1.将数组中的数据臆想成完全二叉树，代码层次不用管
//2.第一次调整比较麻烦（从最后一个非叶子节点框框开始，从右向左，从下向上去调整）
难点1：最后一个非叶子节点下标怎么求？ 解：通过尾结点的下标(len-1)，子推父((i-1)/2)，从而得到最后一个非叶子节点下标((len-1-1)/2)
进行第一次调整，全部的框都要调整，直到只有一个根节点
for(int i=(len-1-1)/2; i>=0; i--)//i指向框框的开始节点的下标
{
难点2：第四个参数没有规律，则直接给最大值len-1即可
Heap_Adjust(arr, len, i, len-1);
}
//3.此时，经过第2步的调整，已经是一个大顶堆了
//将根节点的值和当前尾结点的值进行交换，然后将尾结点剔除出排序。
//将顶部根结点的值（0号下标）和当前最后一个结点值（len-1-i号下标）进行交换
for(int i=0; i<len-1; i++)//i代表次数 也代表当前根节点的下标
{
//根节点和当前尾结点进行交换
int tmp = arr[0];
arr[0] = arr[len-1-i];
arr[len-1-i] = tmp;
//第4步：重复2,3，调整简单，只需要调整最大的框框
难点3:最后一个参数如何写？即每次调整后尾节点的下标如何确定？
len-1-i代表这一趟排序中尾节点的下标，
这一趟结束的时候，需要将尾结点剔除出排序，所以需要(len-1-i)-1
Heap_Adjust(arr, len, 0, (len-1-i)-1);
}
}
2.4.6 核心难点分析
难点一：如何找到非叶子节点？
最后一个非叶子节点就是最后一个叶子结点的父节点
难点二：调整函数的第四个参数如何确定？
第一次调整为最大堆时最麻烦，需要从倒数第一个非叶子节点开始直到根节点，调整函数的参数 start和end分别是这个框的根节点和孩子节点，start很好确定就是：（len-1-1)/2，end如何确定呢？
难点三：只进行调整最大框时的第四个参数如何写？
len-1-i代表这一趟排序时的尾节点的下标，这一趟结束的时候，需要将尾结点剔除出排序，所以需要(len-1-i)-1
难点四：如何控制是否触底？
定义变量i指向空白格子的左孩子，判断是否小于当前框的结束下标即end, 如果它小于end,说明左孩子下标存在，未越界（合法下标）；如果大于end，说明左孩子下标不存在，发生越界（不合法下标），让i每次指向空白格子的左孩子i=start*2+1，让他与end比较即可！
难点五：空白格子的更新
start要指向新的空白格子start一开始指向空白格子，当较大孩子向上挪动，出现了新的空白格子， 这时start随之更新一下
难点六：调整的退出条件（特殊情况）
两种情况： 1.空白格子没有孩子结点 2.有孩子结点，但是孩子结点值小于tmp
2.4.7 测试
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 12,83,78,91,57,91,72,40,91,79,5,70,12,97,49,1,75,9,71,9,24,73,21 };
int len = sizeof(arr) / sizeof(arr[0]);
Show(arr, len);
Heap_Sort(arr, len);
Show(arr, len);
return 0;
}
2.4.8 算法分析
堆排序的运行时间主要初始构建堆和再重建堆时的反复筛选上。 在构建堆的过程中，因为我们是从完全二叉树的最后一个非叶子结点开始进行构建，将它与其孩子结点进行比较和若有必要的交换，因此整个构建堆的时间复杂度为O(n)。 在正式排序时，第i次取堆顶元素重建堆需要用O(logi)的时间，并且需要取n-1次堆顶数据，所以重建堆的时间复杂度为O(nlog2n)。 所以总体来看，堆排序的时间复杂度为O(nlog2n)。并且由于堆排序对于原始数据的排序状态并不敏感，所以堆排序的时间复杂度无论是最好，最坏，还是平均时间复杂度都是O(nlog2n)。从这点来说， 性能显然要远远好过冒泡，简单选择，直接插入排序的(n^2 )的时间复杂度了。 空间复杂度上，它只有一个用于交换的临时变量，所以空间复杂度为O(1)。 不过由于堆排序中的数据交换是跳跃式的进行，因此堆排序的稳定性是不稳定的。 另外，由于构建初始堆所需的比较次数比较多，所以对于数据量较少的情况不适合。
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(1)
- 稳定性：不稳定
2.5 归并类排序—>归并排序（难）
2.6 交换类排序—>冒泡排序
2.6.1基本思想
每一趟排序，两两比较相邻数据，如果左边值大于右边值，则交换，一轮跑完，则将当前最大值放到了最后边，直到把每个数据排好位置。n个数据需要n-1轮。
- 每轮冒泡不断地比较相邻的两个元素，如果它们是逆序的，则交换它们的位置
- 下一轮冒泡，可以调整未排序的右边界，减少不必要比较
2.6.2算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2.6.3图解算法
2.6.4代码实现
//冒泡排序 时间复杂度O(n^2) 空间复杂度O(1) 稳定性：稳定
void Bubble_Sort(int *arr, int len)
{
for(int i=0; i<len-1; i++)//控制循环趟数 len-1趟
{
//控制每一趟具体的比较过程 j代表两两比较的左值下标 两两比较的右值下标j+1
//for (int j = 0; j < len - 1 - i; j++)
for(int j=0; j+1<len-i; j++)
（j+1是相邻比较的两个元素的右边那个元素下标，它的最大值为len-i,即减去每次已排序好的元素个数）
{
//从左向右 两两比较，如果左值大于右值 则交换
if(arr[j] > arr[j+1])
{
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
2.6.5测试
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 12,83,78,91,57,91,72,40,91,79,5,70,12,97,49,1,75,9,71,9,24,73,21 };
int len = sizeof(arr) / sizeof(arr[0]);
Show(arr, len);
BubbleSort(arr, len);
Show(arr, len);
return 0;
}
2.6.6算法分析
- 时间复杂度为O(n^2 )
- 空间复杂度为O(1)
- 稳定性：稳定 （未发生跳跃交换）
2.6.7如何优化
如果在第i次比较后，整个排序序列为有序序列时，按上述代码，仍然要将剩余轮数比较结束，这就是可以优化的点。
设置一个标记flag，当循环中没有元素相互交换时就跳出循环
void BubbleSort(int* arr, int len)
{
assert(arr != NULL);
for (int i = 0; i < len - 1; i++) //外层循环控制趟数
{
bool flag = true;
//for (int j = 0; j < len - 1 - i; j++)
for (int j = 0; j+1 < len - i; j++) //内层循环控制每趟的元素比较 （j+1是相邻比较的两个元素的右边那个元素下标，它的最大值为len-1,再减去每次已排序好的元素个数）
{
if (arr[j] > arr[j + 1])
{
flag = false;
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (flag == true) //这一趟未发生交换，代表完全有序，直接跳出外层循环，不会进行下一趟排序
{
break;
}
}
}2.7 交换类排序—>快速排序(难，笔试最常考)
非比较类排序算法
2.8 基数排序
2.8.1基本思想
基数排序是非比较的排序算法，是一种借助多关键字排序的思想! 最低位优先法:规定先以最低位关键字对所有数据进行排序，再以次最低位对所有数据进行排序，依次重复，直接最高位对所有数据进行了一趟排序，这时所有数据则完全有序
2.8.2算法步骤
以年龄数据为例，假设数字的最低位是第1位，最高位是第3位.；
- 先按照个位进行排序，放入10个队列，再出队，得到第一次排序结果；
- 再按照十位进行排序，放入10个队列，再出队，得到第二次排序结果；
- 最后按照百位进行排序，放入10个队列，再出队，得到最终的排序结果；
2.8.3图解算法
2.8.4代码实现
//获取num对应位是多少？例如：12345,0 ->5 //123,4-> 0
int Get_Num_finger_shiduoshao(int num, int fin)
{
for(int i=0; i<fin; i++)
{
num = num/10;
}
return num%10;
}
//基数排序主要函数
void Radix(int arr[], int len, int finger)
{
std::queue<int> bucket[10]; //10个桶（队列）申请好了
//将所有值，依次按照对应位的值放到对应的桶内
for(int i=0; i<len; i++)
{
//先判断arr[i]应该存放哪一个桶
int fin = Get_Num_finger_shiduoshao(arr[i], finger);
bucket[fin].push(arr[i]); //在将这个值插入到对应的队列内
}
//此时，for循环结束，代表着所有的值，都放到了对应的桶内(队列内)
int k = 0;//k代表 桶内数据重新向arr写入的时候，写入的位置下标
//从0~9号桶（队列），依次将桶内值取出来放到arr中（按队列的规则）
for(int i=0; i<=9; i++)
{
while(!bucket[i].empty())
{
arr[k++] = bucket[i].front();//获取队头元素值存放到对应数组位置
bucket[i].pop(); //出队，把存放过的数据出队（删除）
}
}
//此时，for循环结束，代表着所有的值,都从桶内，重新放回了arr
}
//基数排序 时间复杂度O(d*n) 空间复杂度O(n)
void Radix_Sort(int arr[], int len)
{
int finger = Get_Num_Finger(arr, len);
for(int i=0; i<finger; i++)
{
Radix(arr, len, i); //当i=0，代表以个位进行一次排序
}
}2.8.5测试
2.8.6算法分析
假设最大值的位数是d：
- 时间复杂度O(d*n)
- 空间复杂度O(n)
- 稳定性：稳定，队列先入先出，未改变数据的顺序
2.8.7优缺点
很明显，基数排序与数据的位数有关，位数越多，排序的趟数就会越大，因此基数排序适用于数据的位数相差不大的情况下。
三、排序算法复杂度及稳定性分析
