【数据结构】排序算法（中篇）·处理大数据的精妙
https://i-blog.csdnimg.cn/direct/365df5145b444848a59b9e9018a00c0d.gifhttps://i-blog.csdnimg.cn/direct/c2c35d94128d4e0f8d7aa75115a4e111.gif
前引：在进入本篇文章之前，我们常常在利用某个应用时，会出现【商品名称、最受欢迎、购买量】等等这些榜单，这里面就运用了我们的排序算法，作为刚学习数据结构的初学者，小编为各位美满了以下几种排序算法，包罗了思路拆解，如何一步步实现，包罗了优缺点分析、复杂度来历，种类很全，下面我们开始穿梭算法排序的迷雾，寻求真相！
堆排序
说到堆排序，我们又必要重温树的神奇了，各人先别畏惧，区区堆排序小编将带着各人解构它，让它毫无保留的展现给各人！在学习之前，我们必要知道两种头脑结构：物理结构、逻辑结构
堆实现的逻辑结构就是一颗完全二叉树：
https://i-blog.csdnimg.cn/direct/bb5eaf0d1b8c46208916101dce0021bf.png
但是咱们是用数组实现的，只是借助逻辑结构去完成物理结构，各人对比两幅图，就明确了！
https://i-blog.csdnimg.cn/direct/11c7d67d36ef4a61927a2d745be38e26.png
算法思路：
在看算法思路之前，我们必要知道什么是大顶堆，什么是小顶堆
大顶堆：每个节点的值都大于或便是其子节点的值，堆顶为最大值
小顶堆：每个节点的值都小于或便是其子节点的值，堆顶为最小值
咱们的堆本质是一颗用数组实现的完全二叉树，下面我以数组下标从1开始存储为例，如需更多的参考以及深入学习堆，可以参考小编主页的【堆】哦！下面是各节点下标换算的关系：
左子节点：2 * i 右子节点：2 * i + 1 父节点：i（若已知子节点 k ，则父节点为 k / 2）
堆的算法思路就是：利用堆的性质，来实现对数据的排序
（白话文明确：利用堆结构关系，对数据按照最大堆/最小堆提取堆顶元素来实现排序，因为堆顶是这组数组的最值，咱每次提取出来，不就是达到了排序结果吗！）
实现步骤：
咱们堆排序以实现堆为主，因此必要先手搓一个堆，堆的实现包罗以下步骤：（实现有详细说明）
初始化 存储 上浮调整 移除堆尾元素 下沉调整
复杂度分析：
堆分为建堆、排序堆两个阶段，因此必要分别说明，参考如下明确
建堆阶段：从末了一个非叶子节点开始调整，时间复杂度为O（n）
排序堆阶段：每次调整堆的时间复杂度为O（logn），共必要调整n-1次，因此总时间复杂度为O（nlogn）
综合起来就是O（nlogn）
空间复杂度为O（1）。因为堆排序是原地排序算法，仅仅必要常数级的额外空间
代码实现：
建堆：
咱们按照堆排序的步骤，第一步必要先建立堆，咱们先建立一个结构体，参考如下代码：
#define MAX 10
typedef struct Pile
{
//存储的数组空间
int* space;
//当前堆存储数量
int size;
//当前最大存储量
int max;
}Pile;
下面我们对堆进行初始化操作，开发空间、设置初始变量，参考以下代码：
//初始化堆
void Preliminary(Pile* pilestruct)
{
assert(pilestruct);
pilestruct->size = 0;
pilestruct->max = MAX;
//开辟空间
pilestruct->space = (int*)malloc(sizeof(int) * MAX);
if (pilestruct->space == NULL)
{
perror("malloc");
return;
}
}
接下来咱们进行数据存储进堆，来实现存储的代码：
//存储
void Storage(Pile* pilestruct,int data)
{
assert(pilestruct);
//先判断是否存满，是则扩容
if ((pilestruct->size+1) == pilestruct->max)
{
int* pc = (int*)realloc(pilestruct->space, sizeof(int) * (pilestruct->max) + MAX);
if (pc == NULL)
{
perror("realloc");
return;
}
pilestruct->space = pc;
//更新max
pilestruct->max += MAX;
}
//存储数据
pilestruct->size++;
pilestruct->space = data;
//上浮调整
Adjust(pilestruct->space, pilestruct->size);
}
存储之后必要数据满足最大堆的性质，以是咱们还必要一个调整函数，其头脑如下：
将此数据与其父节点进行比较，如果这个数据较大，交换父节点与其位置，反之不交换，代码如下
//上浮调整
void Adjust(int * space, int child)
{
//父节点下标
int parent = child / 2;
while (child > 1)
{
if (space > space)
{
Exchange(&space, &space);
//更新child，parent
child = parent;
parent = (child ) / 2;
}
else
break;
}
} 现在咱们的建堆就写完了，我存储了几个数字，各人可以看看结果：
https://i-blog.csdnimg.cn/direct/15527b9631f3485f842cde72742013ec.png
排序堆：
将堆顶元素（最大值）与堆的末了一个元素交换，然后size--，这样我们就去除了堆顶元素（最大值），注意：这里的去除只是将堆元素个数减一，并不是删除。然后我们就不停重复这样的操作，直到将所有元素调整完，我们堆的元素原来是9 8 6 1 0 2，调整之后是：0 1 2 5 6 8 9
https://i-blog.csdnimg.cn/direct/12f3867205cf4c14a7817f84e014bd47.png
焦点头脑（重点）：利用多次下沉调整每次将最大值放到末了，这样就达到了有序数据
void Pilesort(Pile* pilestruct)
{
assert(pilestruct);
//parent下标
int parent = 1;
//child下标
int child = 2*parent;
//最后一个节点和根节点换位
Exchange(&pilestruct->space, &pilestruct->space);
//移除根节点
pilestruct->size--;
//下沉调整
while (child <= pilestruct->size)// 注意点1
{
//找到左右孩子节点的最大值
// 注意点2
if (child < pilestruct->size && pilestruct->space < pilestruct->space)
{
child++;
}
//看是否交换其与父节点
// 注意点3
if (child<=pilestruct->size && pilestruct->space > pilestruct->space)
{
Exchange(&pilestruct->space, &pilestruct->space);
//更新父、孩子节点下标
parent = child;
child = 2 * parent;
}
else
break;
}
}
在上面的代码中，有3个必要注意的地方（上图标出来了），为哈3个判断条件必要注意？
注意点1：当堆末了只有2个元素的时间，还要发生一次交换（0与1），因此可以取等号
注意点2：这个 if 条件必要注意，当末了两个元素0与1时，1在根节点，0在子节点，固然满足中国 判断条件，但是以是这两个数字不能发生交换，以是不能取等号
注意点3：还是跟上个判断条件一样，0在根节点，1在子节点，满足判断条件，必要交换
总结：堆的实现必要两次调整。一次是存储数据时必要满足最大堆的性质，必要做上浮调整。而 每次交换根节点元素 和 尾节点元素之后，还是必要保持大顶堆的性质，因此必要下沉调整
下面我们已经将这组数据利用下沉调整完全实现了有序，只必要再依次拿出来就行了
优缺点分析：
堆排序属于原地排序，对大规模数据排序效率较高，而且不会因为数据量增大导致性能急剧下降，但是堆排序同时也黑白稳定排序，雷同元素的相对次序大概会改变，最大的标题就必要手动写一个堆，必要对指针、数组之间的逻辑、物理关系的相互转化
冒泡排序
“冒泡”排序的实现思路很简单，咱们先看一个图：
https://i-blog.csdnimg.cn/direct/1f51c1eb78d64cf2ae8f03b1c5413df3.png
当各种小泡泡从鱼嘴里面吐出来到达最上面的水层，泡泡是最大的，因此咱们冒泡排序的实现也是，每次排序将最大值向后面靠，话不多说，进入正题！
算法思路：
通过重复遍历列表，比较相邻元素并看是否进行交换，将最大的元素逐渐“冒泡”到列表末了
实现步骤：
记着咱们的排序先从单趟写，由里向外。
单趟的实现：通过 for 循环将第一次遍历的最大值通过比较移到末了即可
单趟实现完后，咱们已经排序完了一个元素，那么只必要将剩余的 n-1 个元素排序完成绩行了
https://i-blog.csdnimg.cn/direct/c30b29b39d30442a90a6789657aaa19e.gif
复杂度分析：
最好最坏都是遍历（可以参看“代码实现”），以是时间复杂度都是O（n^2）
空间复杂度：冒泡属于原地排序，以是为O（1）
代码实现：
按照实现步骤，咱们先实现单趟：（对比左右两幅图，我们已经将 9 排序到了末了）
//单趟
for (int i = 0; i < size - 1; i++)
{
//如果前一个元素比后一个元素大
if (arr > arr)
{
Exchange(&arr, &arr);
}
} https://i-blog.csdnimg.cn/direct/e55391eca79e4f06bd1aea70642a6f40.png
我们已经排序完了一个元素，下面我们再套个循环，排序剩余的 n-1 个元素：
for (int j = 1; j < size - 1; j++)
{
//单趟
for (int i = 0; i < size - 1; i++)
{
//如果前一个元素比后一个元素大
if (arr > arr)
{
Exchange(&arr, &arr);
}
}
} https://i-blog.csdnimg.cn/direct/34f921b833a248f0ba91c42d6b54773d.png
代码优化：
我们在优化之前不管后面的元素是否已经有序，都必要遍历，导致重复了无用的次数，优化如下
如果我们开始假设整组元素都是有序的，也就是 false = -1 ，如果发生了交换，那么 false = 1 ，那么就表明必要进行下一次的循环判断，否则直接退出循环，因为遍历一遍结束之后，false如果还为-1，就表明数组已经是有序的了，代码如下：
for (int j = 1; j < size - 1; j++)
{
//假设整组数据有序
int false = -1;
//单趟
for (int i = 0; i < size - 1; i++)
{
//如果前一个元素比后一个元素大
if (arr > arr)
{
Exchange(&arr, &arr);
//假设不符合
false = 1;
}
}
if (false == -1)
{
break;
}
} 优缺点分析：
冒泡排序是稳定的排序算法，相等的元素在排序之后依然保持原来的相对次序，但是时间复杂度原先很高，达到了O（n^2），但是我们通过优化，进步了一定的算法效率，在处理数据时可以扫除有序数据，表现更好
Hoare排序
Hoare排序是快速排序的一种经典实现，由Tony Hoare于1960年提出，焦点头脑是基于分治计谋，通过Hoare分区方法将数组分为两部分，递归的再对子数组排序，看不懂没有关系，咱们学习Hoare排序肯定要知道它咋来的，以上是术语，下面我们进行学习！（特别提醒！很不好明确！）
算法思路：
Hoare排序的关键在于Hoare分区方法，其特点是通过双指针从数组两端向中心扫描，淘汰冗余交换，尤其擅长处理重复的元素，整体分治思路如下：
分别：选择一个基准值（pivot），将数组分为两部分，左半部分元素 <= pivot ，右半部分元素 >= pivot
递归：对左右两部分分别递归调用Hoare排序
https://i-blog.csdnimg.cn/direct/dc7069aba55e48b9a455901b44d672f7.gif
复杂度分析：
每次递归将数组分为两部分，递归深度为 log n ，每层处理时间为 O（n），因此均匀时间复杂度为（n logn）
当每次分区完全逆序，递归深度为 n ，最坏环境达到了 O（n^2）
实现步骤：
起首咱们来讲解单趟的实现（重点）：
（1）假设我们开始有一个数组，将它的最左边的值 6 作为基准值 pivot
https://i-blog.csdnimg.cn/direct/0a36a444e7244b86bc2c3a01a84e1e2c.png
（2）现在我们再设置这个数组的最左边的值 和 最右边的值分别为 left 和 right
https://i-blog.csdnimg.cn/direct/7ee4f6764f4642e28431cd8cce3c6187.png
（3）下面我们通过循环找：左边大于便是基准值的元素（找大），右边小于便是基准值的元素（找小），因为我们必要让大于基准值的元素摞到右边，小于基准值的移到左边
注意事项：我们的初志是大的在右边，小的在左边，因此必要从右边开始移动，只有这样，才气保证小于基准值的移到左边来。反之，如果基准值在右边，就从左边开始移动 。 如下：
https://i-blog.csdnimg.cn/direct/9e9ed20682f0425e9c5df8df037d729c.png
（4）将找到的满足条件的元素进行交换 ，如下图：
https://i-blog.csdnimg.cn/direct/dcb2a9d8ec994fffb5d0d90ae0f6dbf8.png
（5）继续循环找到满足条件的两个元素，直到两者相遇，然后交换相遇的元素与基准值元素
https://i-blog.csdnimg.cn/direct/11898209457a4943bc2c79bf1e247a29.png
https://i-blog.csdnimg.cn/direct/861f94f115f640b08fa26f4a76d7d416.png
（6）现在我们把数组分为了两组，以 6 为分界限，左边的数字小于便是6，右边的数字大于便是6
然后我们采用递归，两端采用分组进行Hoare排序，随着递归函数的调用，这两个组又会分为几个小组，因此我们必须要弄清晰单趟的思路。注意left、right、pivot必要更新，
平凡明确：明确成数，树根就是一整个数组，它会分为很多个子数组（这就是对这里分组的明确）
https://i-blog.csdnimg.cn/direct/44f3db1e4e7a4f6db42af4724a4da6de.png
https://i-blog.csdnimg.cn/direct/5f38d733ee9f4487a0100718f5d83595.png
代码实现：
按照上面的思路，我们先实现单趟，也就是先排序一个元素：（我再夸大一下注意点）
（1）pivot 作为下标开始是 left 的位置，这里不要写死为0，因为我们递归是必要灵活变革的， pivot的开始位置应该是 left 的位置
（2）基准值在左边，就从右边开始找；基准值在右边，就从左边开始找
（3）大循环条件就是它们相遇制止；下面的两个子循环：起首判断大小我就不解释了，之以是加 上 left < right ，是因为制止left 与 right 不停走，出界（发起画图最好明确）
（4）记得更新相遇位置为新的 pivot
int pivot = left;
//单趟
while (left < right)
{
//左边找大于等于基准值的元素（找大）
while (left<right && arr>=arr)
{
right--;
}
//右边找小于等于基准值的元素（找小）
while (left<right && arr<=arr)
{
left++;
}
//找到之后进行交换
Exchange(&arr, &arr);
}
//交换基准值和相遇的元素
Exchange(&arr, &arr);
pivot = left; 上面我们已经实现了单趟， 下面我们来实现递归，这里有2个注意要点：
（1）我们的left-- right++ 每次排序已经移到了一起，但是我们每次递归必要从原先的位置开始（这里我不好用语言形容，各人看下面的图！）以是咱们必要记录left right的初始位置，每次调用函数可以初始化
（2）我们递归必要有结束条件，这个结束条件就是left <= right ，我们循环的条件刚好是left > right，反过来就行！
递归的实现，我们知道第一组结束之后，我们左边的分组起始地点是left，末了是pivot-1；我们右边的分组初始为pivot+1，末了是right（如下图明确）
第一次排序结束
https://i-blog.csdnimg.cn/direct/e1a1b3ee35744f98978fc081df96d0dc.png
第n次排序开始
https://i-blog.csdnimg.cn/direct/eadf7abbaecb4959b7a7f66d2b8a2174.png
https://i-blog.csdnimg.cn/direct/083738ea12c34cea9e91c6b933b708ef.png
void Hoare(int* arr, int left, int right, int size)
{
assert(arr);
//递归结束
if (left >= right)
{
return;
}
//记录
int begin = left;
int end = right;
int pivot = left;
//单趟
......
//调用递归
//左边
Hoare(arr, begin, pivot - 1, size);
//右边
Hoare(arr, pivot + 1, end, size);
} https://i-blog.csdnimg.cn/direct/8e44b784233d4a508d5b8bb2a54eb9ba.png
代码优化：
起首我们看下面这个标题：
每次选 pivot 都是选的数组的初始位置，然后不论有序还是无序，每次分区只能淘汰一个元素，导致递归深度为O（n），时间复杂度写死了为O（n^2）
优化方式：如果我们随机选择 pivot 那么可以使得最坏环境发生的概率为 n^2 / 1，从而保证均匀时间复杂度为 O（n logn）
解释：为哈选择随机位置之后必要交换 pivot 处的数据与数据开始的位置？
（1）简化逻辑分区，我们是将基准值的位置作为分区的起点，左分区从【left ，pivot-1】开始移动，探求大于便是基准值的元素；右分区从【pivot+1 ， right】开始移动，找小于便是基准值的元素
（2）制止额外判断，如果基准值保留在原位置，分区时必要处理pivot跨越数组界限的标题，交换到初始位置后，分区逻辑只必要关注左右left right的移动
//记录
int begin = left;
int end = right;
//随机生成下标
int randIndex = left + rand() % (right - left + 1);
//交换生成的下标与数组初始位置
Exchange(&arr, &arr);
int pivot = left; 优缺点分析：
Hoare排序是一种高效的均匀O（n logn ）排序算法，原地排序，适合大数据，但是它属于不稳定排序，未优化之前大概出现O（n^2）的时间复杂度，总的来说优化性能更佳，处理重复元素表现更好
小编寄语
数据排序的精妙还未结束，【上篇】的算法对比【中篇】，难度又提升了！但是小编已经将思路进行了拆分讲解，相信看几遍也可以明确，再也不消担心自己在哪个细节会犯错了！随着难度的升级，【下篇】将更加精彩，是指针排序？还是又是你从未见过的新排序？关注我，带你揭开【下篇】的面纱！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]