5bei.cn大模型教程网
每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
绪论：
本章将先从简单的两个选择和计数排序上手，然后再到常用常考的快排、归并以及堆排序。内容较多同时附有图片方便理解，以及附带源码和测试地址，让你快速上手练习，建议可以跳转了看自己感兴趣的优先观看或者收藏起来慢慢鉴赏：）
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。
上一篇排序入口常见常考八大排序 上 – ＞ 插入、希尔、冒泡排序
思维导图：
1. 选择🤓排序
核心思想👻：
选择 选择，选择排序的灵魂就在于选择，选择出较小或较大的值放到数组的最开始或者最后的位置，然后缩小选择范围，直到将整个数组选择完成。那么它的算法过程，本质就是在找到最大/最小的值然后放到数组的开始和结尾。
细节🫠：
- 使用双指针同时从前和从后开始遍历整个数组，这样每一次遍历就能找到两个最大最小的值
- 每次找到后要缩小范围，也就是将最大最小值放到最前和最后之后，需要将这两个值不纳入下一次遍历中，那么就需要记录一下开头和结尾
- 其中最需要注意的一点是在最后的交换处，当最大值刚好在start开始处时，需要特殊处理下，防止在最小值交换时（需要使用到start位置），把最大的值移动了位置（这里建议结合代码来看👓）
源码实现🗒️：
void SelectSort(vectorint>& arr)
{
int start = 0,end = arr.size() - 1;
while(start end)
{
int max = start,min = end;//记录的事位置
for(int left = start,right = end; left end && right >= start;left++,right--)
{
if(arr[left] > arr[max]) max = left;
if(arr[right] arr[min]) min = right;
}
//找到当前的最大最小值后，与当前的首位置尾位置进行交换
// 错误示范：当直接交换时会出现上述说的max在start上的问题
//if(start != min && max != start) swap(arr[max],arr[start]);
//if(min != end) swap(arr[min],arr[end]);
swap(arr[start],arr[min]);//先直接将最小值放到开始位置
if(max == start) //**特殊处理下**：若最大位置刚好在start上
{
max = min; // 将max赋值为min的位置
//因为前面 min 和 start 开始交换了值，所以max指向的start就跑到了min上
}
swap(arr[end],arr[max]);//将最大位置放到最后
start++;
end--;
}
}
2. 计数🧮排序
核心思想👻：
计数排序的本质是通过空间换时间，将原本需要同时套用两层的循环解开，变成各自单独的循环，这在程序运行中，两层套用的循环和两个单独的循环效率是远远不一样的，它们是 O(N2) 和 O(N) 的差别。回到计数排序，它的思想就是先遍历一遍数组，并记录数组中元素的出现情况，如有3个1、5个2、7个8。这样记录后再从记录的数组中从左往右的取这些数这样就能得到一个有序的了。（1、1、1、 2 、 2、 2 、 2 、2 …）
细节🫠：
- 通过遍历数组找到最大最小值，从而确定数组的大小范围
- 使用的下标是通过运算得出来的，因为使用值运算得到下标能很好的节省一定的空间，其中主要是使用到最小的值来进行计算，因为 当前值 – 最小值 = 当前下标（最小值 – 最小值 = 0） 也代表其余值减掉最小值就能找到对应的下标，并且当前下标 + 最小值 = 当前值（0 + min = min）
源码实现🗒️：
//计数排序
void CountSort(vectorint>& nums)
{
//计数排序的本质需要通过一个空间来记录当前的数组内部的元素情况
//1. 先确定一个数组范围
//遍历数组找到最小值和最大值，范围就是 max - min + 1
int max = INT_MIN,min = INT_MAX;
for(auto i : nums)
{
if(max i) max = i;
if(min > i) min = i;
}
const int range = max - min + 1;
vectorint> hash(range);
//再遍历一遍循环将所有值的个数添加进去
//其中注意的是：下标要减去最小值,这样每个值就能找到对应的下标
for(auto i : nums)
hash[i - min]++;
//最后将这个数组填充进源数组即可
int cur = 0;
for(int i = 0 ; i hash.size();i++)
{
while(hash[i]--) nums[cur++] = i + min; //hash[i] 内部存的就是当前位置的值的个数
}
}
3. 快速🚗排序
核心思想👻：
快速排序的核心思想就在于将一个数组划分成多个区间，然后再分别处理这些区间。处理过程主要就是首先确定一个key，现在假设是排升序，那么就需要将比key值小的都放到key值左边，比key值大的都放到key值右边。
对于快速排序中确定key值以及通过key值进行划分区间有多种方法，这里主要描述三色划分，因为其他如：Hoare法、挖坑法、前后指针法都比较常见了，并且三色划分在一定程度上效率也会更高
下面默认为升序：
-
hoare法（又称左右交换法）：通过左右指针来进行查找比key值大和小的值，其中key值默认为最左边区间的值，查找过程中，先走右指针right找到较小值后，再走左指针找到较大值，然后进行交换。最后左右指针相撞出循环时，再将key值位置和相撞位置进行交换。
-
挖坑法：算是hoare法的优化，通过先一个坑位的设置减少了最后key值和相撞位置的交换。首先默认最左值为key值并且为坑位，以及需要单独记录key值方便后续使用，然后先走右指针找到较小值，将当前值填充到上一个坑位，然后将当前位置记录为新坑位，然后再走左指针，找到较大值，填充到上一个坑位，记录为坑位，然后再到右指针，依次往复。直到最后相撞，最后将最开始记录的key填充到最后一个坑位即可。
-
前后指针法：通过从快慢指针，从前往后遍历的方式来将数组区间划分。具体逻辑为：使用一个快指针遍历整个数组找到比当前key值小的元素，然后慢指针先向前移动一位（慢指针的作用是记录小于等于key值的最后一个位置，它默认是指在key值上的，当发现了新的小于key的元素时，就需要先移动在交换），然后再与快指针交换，以此往复，直到快指针走完为止，最后慢指针的位置再和key值进行交换（此处的交换不会出现问题，因为慢指针的定义就是指向小于等于key的最后一位）。
-
三色划分：三色划分的划分区域和前面的三种略有不同，三色划分是将区间划分成了三个，分别是（小于 | 等于 | 大于 ），这样做的好处是，当遇到非常多相等的元素时就能提高非常多的效率，避免再次处理等于key值的值，因为在上述几种方法中他会仍然处理相同的值。
快排实现以及三色划分的更多细节可以见这个blog，这个内部还配有几道练习辅助你了解快排
细节🫠：
- 其中的key，我们可以通过随机数的形式获取，因为这样能避免类似降序的数组让key值取到最大导致划分区间畸形
- 其中要注意三色划分中三个指针的定义和移动：
- l指针指向的是最后一个小于key的值的位置，所以初始为left – 1，要先加加再交换
- 同理 r指针指向的是第一个大于key的值的位置，所以初始化为 right + 1，要先–再交换
- 而i指针用于遍历数组，主要要注意的是当 i 和 l 交换时 i 继续移动，而 i 和 r 交换的时候 i 不变，这是因为 l 指针指向的位置是遍历过了的，所以交换后 i 继续往后走，而 r 位置的值是没有判断过的，还得再判断下，所以不能 i++
源码实现🗒️：
int getRandomVal(int left,int right)
{
int ram = rand() % (right - left);
return left + ram;
}
void quickSort(vectorint>& nums,int left,int right)
{
if(left >= right) return ;
// 快排 + 三色划分 + 随机取值
int key = nums[getRandomVal(left,right)];
// 三色划分：划分为 大于 等于 小于 key的三块区间
int l = left - 1, r = right + 1 , i = left;
while(i r)
{
// 若扫描到的i位置id值 > key 将其移动到l左边
if(nums[i] key) swap(nums[++l],nums[i++]);// l先++，然后交换i位置的值，然后让i继续往后
else if(nums[i] > key) swap(nums[--r],nums[i]);// 此处同上，r先--，不过注意的是 i 不动，因为交换过去后的right位置的值是没有判断过的
else i++;
}
// 不断缩小范围
quickSort(nums,left,l);
quickSort(nums,r,right);
}
vectorint> sortArray(vectorint>& nums) {
// 生成随机数种子
srand(time(NULL));
QuickSort(nums,0,nums.size()-1);
return nums;
}
4. 归并🍪排序
核心思想👻：
归并排序顾名思义：归的时候进行合并，而归的前提就是递归，先不断的缩小范围当范围缩到最小后进行返回（归），如下图（先蓝色箭头缩小范围，当到达最小范围，然后绿色箭头返回并进行合并）
从上图也不难看出代码实现的逻辑：
- 将一个数组不断的划分为左右区间，直到各自只剩一个值时返回
- 返回到上一层时因为只有一个值所以就代表是排序好的，现在对这两个排序好的数组进行操作，将他们合并为一个数组
- 这样就形成了一个新的排序好的数组了，再返回到上一层
- 以此往复，直到最顶层返回结果
这里还有篇练习文章内部也附有了很多细节blog
细节🫠：
- 对于归并排序来说，需要使用一个数组，来存储零时的合并的值，因为此处一直都是在本身nums上进行的操作，若直接附到原数组上会导致覆盖原数组数据所以借用一个临时数组存储合并结果最后赋值到原数组即可
- 合并的过程本质就是一个将两个数组合并成一个有序的过程：使用两个指针遍历两个数组，将大的值放到临时数组中
- 因为是遍历两个数组，所以只要一个数组遍历完成了就不再遍历了，此时就有可能会导致其中一个数组中的值并没有完全遍历完，那么此时就需要防止这种情况，那么再添加两个循环保证每个数组的完全取完
源码实现🗒️：
class Solution {
public:
const static int N = 5e4 + 10;
int temp[N];
void MergerSort(vectorint>& nums,int left,int right)
{
//当只有一个值时结束
if(left >= right) return;
//将数组划分为两份
int mid = left + (right - left) / 2;
//分别排序左右两块区域
MergerSort(nums,left,mid);
MergerSort(nums,mid+1,right);
//合并两块区域,方法遍历两块区域
int l = left,r = mid+1;
int i = l;
while(l mid && r right)
{
if(nums[l] nums[r]){
temp[i++] = nums[l++];
}
else{
temp[i++] = nums[r++];
}
}
//处理剩下的内容
while(l mid) temp[i++] = nums[l++];
while(r right) temp[i++] = nums[r++];
for(int i = left; i right;i++)
{
nums[i] = temp[i];
}
}
vectorint> sortArray(vectorint>& nums) {
MergerSort(nums,0,nums.size()-1);
return nums;
}
};
5. 堆🪐排序
核心思想👻：
认识堆的前提是你得认识树（若没了解强烈建议先看建议这篇blog），堆的核心是在树基础上完成的，堆的结构是一个特别的树，并且它还分为了大根堆和小根堆
- 大根堆：顾名思义 根比较大 的堆
- 小根堆：则相反 根比较小 的堆
而在使用堆排序的前提就是先建立好堆（俗称建堆）
建堆：在了解建堆前咋们认识到了 大根堆 和 小根堆 的简单定义，现在就需要继续了解一个辅助建堆的方法：向上/向下调整法
这里讲述的是小根堆
- 向上调整：顾名思义自底向上的调整堆，具体来说就是自身为树的 子节点 然后和 根节点（父节点）进行比较，根节点跟小则进行交换，反之则不。当交换后来到了根节点，那么此时还需要继续往上调整，就需要把自身改为 子节点 并且重新定义父节点
- 向下调整：和上面类似，只不过现在自身是 根节点 和 子节点 进行比较，比较若子节点跟小则进行交换，然后将自身变成子节点，在不断往下。
了解了向上和向下调整后，并不是就能建堆了，而是需要知道现在给你一个随机的数组，你需要从那个结点开始进行向上或向下调整来建堆，以及需要知道应该如何走才能将整个数组都建立为一个堆
方法：
- 首先对于拿到的一个数组，此时看待数组就不是数组了，而是把他抽象成一颗二叉树（过程也很简单如下图）
- 对于向上调整来说：从最后一个节点开始
- 对于向下调整来说就是从：第一个非叶子结点开始（叶子结点就是无子节点的节点，非叶子节点则相反，上图的第一个非叶子结点就是 7）
现在已经将一个随机的数组建立成了一个堆，那么就可以开始了解堆排序了
堆排序，本质就是在大根堆或者小根堆上的一些操作，让这个堆的数组变成一个有序的数组
具体实现：
- 将堆顶的元素和最后一个元素进行交换
- 然后将最后一个元素抛出于堆中（这里意思是将堆最后一个元素看成之前的倒数第二个元素，相当于这个元素后面不再进行堆内的处理了），有一个计算公式 （n – 1） / 2 就能快速找到第一个非叶子节点的位置
细节🫠：
- 父节点和子节点的关系：
- 第一个子节点：child = parent * 2 + 1
- 第二个子节点：child = parent * 2 + 2
- 父节点：parent = child / 2（不用 +1 / +2 是因为除2后是一样的）
- 并且注意的是，我们使用的节点本质就是数组的下标！
tips📕：忘记时建议拿最简单三个节点的二叉树来快速得出
- 在向下调整的过程先默认使用第一个节点，在循环中在和第二个元素进行判断，这样就不用每次都判断两个再取出一个了
- 最后附一点堆排序中：
- 建立大根堆排序为升序
- 建立小根堆则排序为降序
- 因为你需要知道每一次循环过程中会取出最后一位，而大根堆每次取出的都是根中最大的
源码实现🗒️：
排序数组：
//大根堆
void downAdjust(vectorint>& nums,int parent,int n)
{
int child = parent*2 + 1;
while(child n)
{
if(child + 1 n && nums[child + 1] > nums[child])
{
child++;
}
if(nums[child] >= nums[parent])
{
swap(nums[child],nums[parent]);
}
else
{
break;
}
parent = child;
child = parent*2 + 1;
}
}
void InitStack(vectorint>& nums)
{
int n = nums.size();
// 找到第一个父节点，从第一个赋权结点开始做向下调整
for(int parent = (n - 1) / 2; parent >= 0 ; parent--)
{
downAdjust(nums,parent,n);
}
}
void HeapSort(vectorint>& nums)
{
//1. 建堆，升序建大堆，因为最大的元素放到最后后就抛出了，这样不断的添加到最后一个上最终形成升序
InitStack(nums);
//2. 完成堆排序
int end = nums.size();//从最后元素的个数
while(end > 1)
{
//1. 交换
swap(nums[0],nums[end-1]);
//2. end最后一个元素discard抛弃
end--;
//3. 向下调整
downAdjust(nums,0,end);
}
}
vectorint> sortArray(vectorint>& nums) {
HeapSort(nums);
return nums;
}
本章完。预知后事如何，暂听下回分解。
如果有任何问题欢迎讨论哈！
如果觉得这篇文章对你有所帮助的话点点赞吧！
持续更新大量C++细致内容，早关注不迷路。
文章来源于互联网:常见必备八大排序 下(重头戏)–＞选择、计数、快排、归并、堆排序
