数据结构 —— 图文并茂的——> 堆排序, 直接选择排序
每博一文案
这段旅程，路途艰辛而漫长，我们都希望自己的心酸，有人能懂，委屈的
时候，有人谈，但随着年龄的增长，慢慢明白了一个道理，永远不要奢望
有人懂你，感同身受是这个世界上最大的谎言，自己的累，始终只有自己最清楚。
即便人潮拥挤，仍要自己踽踽独行，在人生这趟旅程中，有风景，也有风雨，
风景，可与他人说，但风雨只能自己承受，我们所经受的一切，他人难悟，
哪怕你万箭穿心，痛不欲生，也仅仅是你一个人的事情。
别人也许会同情，也许会探索，但永远不会清楚你伤口究竟溃烂到何种境地。
哪怕你的世界发生了一场火灾，大到足以把一切焚烧殆尽，但路过的人
什么也感觉不到。你说生活不易，他会说你矫情，别人怎么没你这么多事，
你想要倾诉烦恼，他却告诉你，不如意是人生常态。
成年人的世界就是如此，你越是希望一个人懂你，，你得到的失望就越多，
世上没有脉络相同的树叶，也没有绝对契合的两个人。
不要奢望别人懂你，生活的酸甜苦辣，自己尝过才是味道。
当你能独自度过，那段黑暗时光后，日子会变得熠熠生辉。
—————— 一禅心灵庙语
文章目录
堆的概念
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树的逻辑形式存在的
- 堆在逻辑上是一棵 完全二叉树
- 堆在物理上是一个 数组
如下是堆的示图: 堆(逻辑上的完全二叉树) 与 堆(物理上的数组) 之间的关系
- 左孩子: 左孩子在数组上的下标位置 = 父节点所在的下标位置 * 2 + 1：leftChild = parent * 2 + 1
- 右孩子: 右孩子在数组上的下标位置 = 父节点所在的下标位置 *2 +2 ：rightChild = partent * 2 + 2
- 父节点: 父节点在数组上的下标位置 = ( 左孩子或右孩子的下标位置 - 1 ) / 2 : parent = ( child - 1 ) / 2
右孩子在数组上的下标位置 只是 比左孩子上的下标位置 多 + 1了，反过来：左孩子只是比右孩子下标位置 少了个 1 ，这一点可以运用在 左右孩子之间的转换变换上
堆是具有以下性质的完全二叉树：
大顶堆/大堆 : 每个父节点的值都是要 大于或等于 其左右孩子的节点的值的，注意 :没有对左右孩子它们之间的大小关系做要求。其中 大顶堆 的堆顶数值最大
大顶堆图示
小顶堆/小堆 : 每个父节点的值都要 小于或等于 其左右孩子的节点的值的，同样 没有要求左右值的大小关系 。其中 小顶堆 的堆顶数值最小
小顶堆图示
问题:
请问如下数组 [101,88,46,70,34,39,45,58,66,10] 是堆吗 ？？? 是的话又是什么堆 ？？？
解题思路：其实十分简单，因为堆，无法就是 大顶堆，和小顶堆吗，把数组从 编号 0 开始一层一层的列出完全二叉树后，再根据大小堆的特性判断是否，是其中的一种，是说明是堆，大小堆都不是的话就不是堆了。如下:
从上图观察：我们可以看到其中的 所有的父节点 >= 孩子节点的数值，所以是大堆无疑了。
堆排序算法
堆排序的基本思想
这里我们主要以升序为例子
- 将待排序序列构造成一个大顶推
- 数组升序建大顶堆，具体原因后面会说明
- 数组降序建小顶堆，具体原因后面会说明
- 此时：整个序列的 最大值就是在堆顶的根节点处了
- 将其 根节点的数值与末尾的元素的数值交换 ，此时末尾就是最大值了(就是数组的最后下标位置)
- 然后将剩余 n -1 个元素重新构造成一个大顶堆，就是从逻辑上把数组中最后一个已经排好序的数值从堆中除去重建一个大顶堆，此时的 数组中次大的数值就是在堆顶的根节点处了 ，再将其 根节点的数值与末尾的元素的数值交换 ，此时数组倒数第 二的下标位置就存发的是次大的数值了，如此反复，便能得到一个升序的序列数组了
具体思想动图如下:
向下调整算法(以建大顶堆)
向下调整算法思想 (以建大顶堆为例子)
首先我们需要知道 可以使用向下调整算法有一个 前提条件: 左右子树都为大顶堆 或者是左右子树都为小顶堆，
不满足这个前提条件是不可以使用 向下调整算法 的，这是需要我们注意的点
实现步骤如下 (以建大顶堆为例子)
- 首先从根节点开始，选择当前根节点(父节点)左右孩子中最大的数值
- 选择出后，让其值与 根节点(父节点)的数值比较判断：
- 如比较的结果是：根节点(父节点) 更小的话，因为是以建大顶堆为例的，所以把 根节点(父节点)的数值与 其(左右孩子中的较大的数值) 进行交换；如果根节点(父节点)更大的话，就表示该数组已经调整成了一个堆了，就不用在调整了。
- 如果调整到叶子节点的位置，也说明该数组已经调整成了一个堆了，也不用再调整了
静态图示如下:
原图
向下调整后的:
代码实现
void adjustDwon(int* arr, int n, int root)
{
int parent = root; // 当前的根节点数组下标位置
int child = parent * 2 + 1; // 默认左孩子数组下标位置
while (child < n) // 左孩子 > 数组长度时，循环到达叶子节点停止
{
// child+1 < n 防止右孩子不存在,访问越界了,判断左右孩子那个数值大，取数值大的
if (child + 1 < n && arr[child + 1] > arr[child])
{
// 右孩子大, 变成右孩子
child = child + 1;
}
// 判断父节点是否小于 左右孩子，小于交换
if (arr[parent] < arr[child])
{
swap(&arr[parent], &arr[child]); // 交换数值,传地址,形参的改变影响实参
parent = child; // 继续向下调整,从下面的孩子开始,作为父节点
child = parent * 2 + 1; // 同时更新对应的孩子
}
else // 根节点已经是最大的值了,不用调整了,已经是成堆了,跳出循环
{
break;
}
}
}
代码解析:
while (child < n) ，如下图所示，当其左孩子的下标 > 超过了数组的长度，是不是已经到达了，叶子节点处了，所以应该停止向下调整了。
if (child + 1 < n && arr[child + 1] > arr[child]) : 判断左右孩子之间的大小的时候，我们还需要判断其左右孩子是否存在，不存在的话，我们就是数组越界了。
从前面的循环条件 (while(child < n )) 的判断,已经为左孩子的存在进行了一个判断，
但是我们的右孩子，还没有进行一个判断，所以我们需要对其做一个判断，防止右孩子不存在而越界了。
parent = child;child = parent * 2 + 1 : 更新父节点,以及 孩子，继续向下调整，因为没有该数组还没有成堆，所以需要，继续向下调整，如下图:
向上调整算法:建大顶堆
实际上我们真正需要排序的数组是 不符合 向下调整算法的前提条件的 : 左右子树要为堆。
所以我们是无法使用 向下调整算法为我们建堆的 ，而我们知道 堆排序 的第一步就是建堆，
- 升序，建大顶堆
- 降序，建小顶堆
可我们又无法满足 向下调整的算法前提条件，怎么办呢 ！！！
我们可以利用向下调整的原理， 从最后一个非叶子节点开始调整，从左到右，从上到下进行调整，叶子节点不用调整，自成一个堆，因为没有左右子树嘛 ，如下动图:
而我们有如何找到最后一个不是叶子节点的的下标呢 ？？？
如下图所示，最后一个非叶子节点的下标 就等于最后一个叶子节点的父节点的下标
一个数值往上走，直到下标为 0 就可以了，如下:
我们重新给定一个 无序的数组 如下：注意 这里的操作用数组，树结构只是参考理解
第一个非叶子节点 parent = ( child - 1) / 2 = ( 4 - 1 ) / 2 = 1 也就是 元素为 6 的节点处
比较时：先让 5 与 9 比较，得到左右孩子最大的那个，再和 6 比较，发现 9 大于 6，交换数值
找第二个非叶子节点 下标 – ， 找到 4
比较时: 先让 9 与 8 比较，得到左右孩子最大的，再和父节点 4 比较，发现 9 比 4 大，交换数值
此时的交换后，导致了后面的 [4, 5, 6] 的结构混乱，将其继续调整。
比较是: 先让 5 与 6 比较，得到左右孩子中最大的那个，再和父节点 4 比较
此时，就将一个无序序列构造成了一个大顶堆。
具体代码实现
void heapSort(int* arr, int n)
{
// 建大顶堆
// (n- 1- 1) /2 从第一个非叶子节点的下标向上开始，建大顶堆
for (int i = (n-1-1) /2; i >= 0; i--)
{
adjustDwon(arr, n, i); // 调用向下调整算法
}
}
代码解析:
for (int i = (n-1-1) /2; i >= 0; i–)
(n -1)表示的是数组最后一个下标位置，而我们要从最后一个非叶子节点的位置开始，该下标位置就等于 : 最后一个叶子节点的父节点的下标; 而 (n -1-1) /2 就是最后一个非叶子节点的父节点下标
堆排序，升序
首先我们知道 升序，我们建的是 大顶堆 ，而大顶堆的特点，堆顶 是最大的数值，我们只需要把该数值放到数组的最后面去就可以了，怎么做呢
我们只要将 堆顶元素(最大的数值) 与末尾元素的数值进行一个交换，使其数组末尾元素最大 ，然后我们再对根位置(数组下标 0 处)进行一个堆的向下调整，注意: 其中被我们交换到数组的最后位置的那个数值在逻辑上不要参与向下调整了，它已经排序好了，再调整就乱了 ，我们前面的向上调整算法，已经将数组建成了一个大堆，所以这里我们只是将末尾的一个数值不参与建堆，是没有影响到堆的整体结构的，所以我们可以使用向下调整算法建大堆，求出次大的数值，在新的堆顶 上，再和数组上倒数第二个位置交换数值，这样次大的数值就存放到了，数组倒数第二个位置处，如此反复进行交换，重建，交换 ，直到只有一个数据调整时。就停止，因为最后一个数据，交换也和它自己交换。此时该数组就是一个升序的了。
相关动图如下
将堆顶元素与末尾元素进行交换的步骤如下:
如下给定好一个前面建好的大堆
- 将 堆顶元素 最大的值 9 与 末尾元素 4 进行交换
- 重新调整结构，使其继续满足堆的定义，注意不要把已经交换到末尾的元素加入到调整中，因为该数值已经排序好了，
- 调整好后，将 新堆顶元素 (第二大的值) 8 与 数组倒数第二 的位置 5 交换数值
- 再重新调整，使其继续满足堆的定义，注意不要让已经排序好的数值参与调整，防止打乱了
- 调整好后，将 堆顶元素 6 与 末尾元素 4 ，进行交换
- 最后一次调整，使其继续满足堆的定义，注意 : 不要把已经排序好的元素加入到调整中去
- 最后将 堆顶元素 5 与 末尾元素 ，进行交换，这次交换后，只剩下最后一个数据了，就不用再进行调整交换了，该数组已经是有序的了，升序
总结思路:
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
- 将堆顶元素与末尾元素交换，将最大元素「沉」到数组末端
- 重新调整结构，使其满足堆定义，然后继续交换堆顶与当前末尾元素，反复执行调整、交换步骤，直到整个序列有序
具体代码实现
void heapSort(int* arr, int n)
{
// 建大顶堆
// (n- 1- 1) /2 从第一个非叶子节点的下标向上开始，建大顶堆
for (int i = (n-1-1) /2; i >= 0; i--)
{
adjustDwon(arr, n, i); // 调用向下调整算法
}
int end = n - 1; // 数组的最后下标位置
while (end > 0) // 只剩一个数据，停止调整
{
swap(&arr[end], &arr[0]); // 堆顶 与 末尾交换
adjustDwon(arr, end, 0); // 调整
end--; // 继续向上调整
}
}
总结思路 ：
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
- 升序，建大顶堆
- 降序，建小顶堆
- 将 堆顶元素与 末尾元素 交换，将最大元素
沉到数组末端， - 重新调整数组结构，使其继续满足堆定义，然后继续交换堆顶 与 当前末尾元素 ，反复执行调整，交换步骤，直到整个数组有序
为什么，升序，建的是大顶堆，不是小顶堆
堆排序其实是选择排序的一种，不过它是通过 堆来实现选数的，如果是
建小堆，最小数在 堆顶 ，已经被选出来了。那么要在剩下的数中
再去选数，但是剩下树结构都乱了，需要重新建堆，才能选出下一数
，建对的时间复杂度是 O(N) ,那么这样不是不可以，而是堆排序就没有效率优势了，
还不如直接遍历选数排序。
降序，建小顶堆 ，也是这个道理.
数组建小顶堆
就是和上面 向下调整算法 中的判断和 根节点数值的,比较换成是 小于 号,把左右孩子中更小的数值,和根节点(父节点)的数值比较,如果比父节点更小的话,进行交换, 不停的向下调整.
让父节点的值 小于或等于 其左右孩子的数值
具体代码实现如下:
void adjustDwonSmall(int* arr, int n, int root)
{
int parent = root; // 根节点(父节点) 在数组上的下标位置
int child = parent * 2 + 1; // 默认是左孩子,在数组上的下标位置
while (child < n) // 当左孩子大于数组长度,表示到了叶子节点的位置,同时不可再访问了,不然就是越界了
{
// 左右孩子,取更小的一个,同时需要判断右孩子是否存在,不存在防止越界
if (child + 1 < n && arr[child + 1] < arr[child])
{
// 这里是 右孩子更小,转换
child = child + 1; // 变成右孩子
}
if (arr[child] < arr[parent])
{
// 孩子数值更小,和父节点交换
swap(&arr[child], &arr[parent]); // 交换
parent = child; //继续向下调整
child = parent * 2 + 1;
}
else // 根节点是最小值时，已经调整完了,跳出循环
{
break;
}
}
}
void heapSortDesc(int* arr, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustDwonSmall(arr, n, i);
}
}
堆排序，降序
首先我们知道 降序，我们建的是 小顶堆 ，而小顶堆的特点，堆顶 是最小的数值，我们只需要把该数值放到数组的最后面去就可以了，怎么做呢
我们只要将 堆顶元素(最小的数值) 与末尾元素的数值进行一个交换，使其数组末尾元素最小 ，然后我们再对根位置(数组下标 0 处)进行一个堆的向下调整，注意: 其中被我们交换到数组的最后位置的那个数值在逻辑上不要参与向下调整了，它已经排序好了，再调整就乱了 ，我们前面的向上调整算法，已经将数组建成了一个小堆，所以这里我们只是将末尾的一个数值不参与建堆，是没有影响到堆的整体结构的，所以我们可以使用向下调整算法建小堆，求出次小的数值，在新的堆顶 上，再和数组上倒数第二个位置交换数值，这样次小的数值就存放到了，数组倒数第二个位置处，如此反复进行交换，重建，交换 ，直到只有一个数据调整时。就停止，因为最后一个数据，交换也和它自己交换。此时该数组就是一个降序的了。
void heapSortDesc(int* arr, int n)
{
// 建小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustDwonSmall(arr, n, i);
}
int end = n - 1; // 数组最后位置
while (end > 0)
{
swap(&arr[0], &arr[end]); // 堆顶元素和末尾元素交换
adjustDwonSmall(arr, end, 0); // 重新调整,保持堆的定义
end--; // 继续交换,调整
}
}
选择排序
思路
首先在数组中找到 最小(大)的元素,与数组中的起始下标位置,进行交换,
再从剩余的数组中找到次小(大)的元素,与数组中第二个下标位置,进行交换,
直到,走到数组中只剩一个数据没有排序时,结束,这是常见的一种 选择排序的方式
选择排序一共有 (数组大小 -1) 轮的排序次,
而我介绍的是一种优化的 选择排序 ,上面的那种循环方式一次就只能选出一个数值,我们着这种方式一次循环可以选出 两个数值
定义两个前后下标指针，一前一后的前进，相遇停止
每 1 论排序,又是一个循环,循环的规则是:
- 先假定这个数组中最小的数和最大的数的下标位置都是起始数组下标
- 然后和后面每个数进行比较,如果发现有比当前数更小的数,以及比当前数更大的数，则重新确定最小的数值的下标位置，以及重新确定最大的数值的下标位置，
- 当我们把数组遍历完了，我们就找到了数组中最大数值和最小数值的下标位置
- 交换，把最大的数值放到数组的后面，把最小的数值放到数组的前面，
- 重复，直到 前面两个下标指针相遇，该数组就是有序的了
具体图示如下 :
先给定一个无序的数组，升序排序
- 第一轮找到其数组中的最大值和最小值的下标位置
把最大值 5 与 数组中最后位置 end 的数值交换
但是我们交换后，发现我们原先所找到的数组最小值的下标位置，出现了错误，原先存放在数组最小值的下标位置，被交换后，存放的反而是最大的数值了。这样的话，就会影响后面把最小值交换到数组的前面，反而是把 9 放到了 begin 位置了，显然是不合理的，因为我们是升序。
所以我们需要修正它，min 最小数值的下标，指向最小值，从上图我们可以看到原先 min 存放的 最小值 0 是被交换到了，下标 max 的下标位置，所以我们只要更新，让min 重新指向数组最小值 0 即可，就是 min = max ,
当什么时候会出现这样的情况呢，当 min == end 升序中最小值位于数组的最后面位置 end 的时候就会出现这样的情况， 因为前面把 max 与 end 做了数值交换，导致 原先的 min 位置存放的数值发生了，改变，所以需要修正
修正 min 的合理下标
- 修正号后，交换
把数组中最小值 0 , 与数组起始位置 begin 进行交换，并且 end --, begin ++ 下标移动
- 再进行第二轮循环找到第 2 小的数值下标和第 2 大的数值下标，再进行交换
第2大值max 7 与 end ,进行交换
交换后，发现 min == end ,需要对 min ，进行一个修正
修正好后，进行交换
第 2小的 min: 1 与 begin 进行交换,
- begin ++ ,end – 再循环，找到其数组中最小值,进行交换
- 最后 begin 与 end 相遇了停止交换，循环，该数组已经是 升序的了
选择排序代码实现 升序
具体代码实现如下:
// 交换数值函数
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void selectSortAsc(int* arr, int n)
{
int begin = 0; // 标记一下数组的起始位置下标，数组前面的下标位置
int end = n - 1; // 标记一下数组的末尾位置下标，数组后面的下标位置
while (begin < end) // begin 与 end 下标相遇停止循环
{
int max = begin; // 设定数组中最大数值的下标位置为 begin 数组前面的位置
int min = begin; // 同样把数组中最小的数值的下标位置为 begin ,用于比较数组中的数值
for (int i = begin; i <= end; i++) // 循环找数组中最大数值和最小数值的下标位置
{
// 数组中找到最大的数值的下标位置
if (arr[max] < arr[i])
{
max = i; // 更新最大值的下标位置
}
// 数组中找到最小的数值的下标位置
if (arr[min] > arr[i])
{
min = i; // 更新最小值的下标位置
}
}
// 找到后,跳出循环
swap(&arr[max], &arr[end]); // 把数值最大的放到数组 最后面
if (min == end) // 修正
{
min = max;
}
swap(&arr[min], &arr[begin]); // 把数值最小的放到数组的最后面
end--;
begin++; // 移动下标
}
}
选择排序，降序
选择排序的降序和前面的升序是一样的，过程图我就不画了，只是把前面的交换修改一下就可以了，
把数组中大的数值交换到前面，数值小的数值交换到后面
// 交换数值函数
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void selectSortDesc(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int max = begin;
int min = begin;
for (int i = begin; i <= end; i++)
{
if (arr[max] < arr[i])
{
max = i;
}
if (arr[min] > arr[i])
{
min = i;
}
}
swap(&arr[max], &arr[begin]); // 与升序不同点,把数值大的放到数组的前面去
if (min == begin) // 修正点,不同了,这里先交换的是 begin 的位置了
{
min = max;
}
swap(&arr[min], &arr[end]); // 与升序不同点,把数值小的放到数组的后面去
begin++;
end--; // 下标移动
}
}
选择排序的大缺点
选择排序，时间复杂度为 O(N*N)
选择排序可以说是最差的排序了，因为就算你给的数组是有序的，其时间复杂度还是O(N*N)，
就算是最好的情况下其时间复杂度还是 O(N*N), 总的说就是无论情况好坏，其时间复杂度都为 O(N*N)
堆排序 与 选择排序的性能测试
我们利用计算排序前后的时间差，计算出排序的效率
排序性能 = 排序完的时间点 - 排序前的时间点
// 排序性能测试
void testOp()
{
srand(time(0)); // 时间种子
int const N = 100000; // 10w 空间
// 动态堆区上开辟空间,10W 个
int* a = (int*)malloc(sizeof(int) * N);
int* b = (int*)malloc(sizeof(int) * N);
// 判断动态堆区上开辟空间是否成功
if (NULL == a || NULL == b)
{
perror("malloc error"); // 提示报错
exit(-1); // 非正常退出程序
}
for (int i = 0; i < N; i++)
{
a[i] = rand(); // 生成随机值
b[i] = a[i]; // 赋值,数值一样,控制变量
}
int begin1 = clock(); // 选择排序前的时间点
selectSortAsc(a, N); // 选择排序,升序
int end1 = clock(); // 选择排序结束后的时间点
int begin2 = clock(); // 堆排序前的时间点
heapSort(a, N); // 堆排序,升序
int end2 = clock(); // 选择排序结束后的时间点
/*
* 排序效率 = 排序结束后的时间点 - 排序前的时间点
*/
printf("选择排序: ");
printf("%d\n", end1 - begin1);
printf("堆排序: ");
printf("%d\n", end2 - begin2);
}
从结果上看可以发现其 堆排序 比 选择排序 快太多了，排序的数据量越大其结果就越明显
堆排序 与 选择排序的完整代码实现
下面是 堆排序 与 选择排序 的完整代码实现，大家直接粘贴复制后，可以直接运行，大家可以体验一下
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
// 打印数组
void playArrays(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 传地址,交换数值
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
/* 向下调整算法
前提: 左右子树为堆: 要么左右子树为大堆,要么左右子树为小堆
大堆: 父节点 大于或等于 子节点, 堆顶为最大
小堆: 父节点 大于或等于 子节点, 堆顶为最小
*/
// 建小堆
void AdjustDwonSmall(int* arr, int n, int root)
{
int parent = root; // 父节点的下标位置
int leftChild = parent * 2 + 1; // 默认使用左孩子的下标位置
/* 关于数组下标表示: 父子节点之间的关系
* 左孩子: leftChild = patent*2 + 1;
* 右孩子: rightChild = patent*2 + 2;
* 对于同一个父节点的左右孩子的关系
* 右孩子的数组下标位置 = 左孩子的数组下标位置 + 1
* 父子节点的数组下标位置 = ( 孩子的数组下标位置 - 1 ) / 2
*/
/*
*
当左孩子的数组下标取值： 越界了说明 到达了叶子节点,不可以再向下调整了
leftChild = parent*2 +1
或者
因为是建小堆,所以当父节点是最小的时候,就不用再向下调整了,跳出循环
*/
while (leftChild < n)
{
// 判断左右孩子, 取更最小的和父节点的数值交换
// 同时判断右孩子(leftChild +1)是否存在, 防止右孩子不存在导致数组 越界了
// 左孩子在循环处判断了,是否会越界的可能
if (leftChild +1 < n && arr[leftChild + 1] < arr[leftChild]) // arr[leftChild+1] 右孩子的数组的下标位置
{
// 这里判断的是右孩子小, 则把下标 +1 变成右孩子
leftChild = leftChild + 1; // 左孩子 + 1 = 右孩子的下标位置
}
// 如果孩子数值小于 父节点的数值,交换
if (arr[leftChild] < arr[parent])
{
swap(&arr[leftChild], &arr[parent]); // 注意传地址,形参的改变影响实参
parent = leftChild; // 继续向下调整,更新父节点, 从下一个更小的数值的孩子的下标位置开始
leftChild = leftChild * 2 + 1; // 根据父节点,更新新的左孩子的数组下标位置
}
else // 建小堆,如果 父节点的数值已经是最小的了,就不用再向下调整的
{
// 跳出循环
break;
}
}
}
// 堆排序,降序
void HeapSortDesc(int* arr, int n)
{
/*
实际上我们给定的数组一般都不是堆,
因为不是堆,所以我们无法进行向下调整算法,
所以我们要先,把堆建起了,这里我们
建小堆
从最后一个不是叶子节点的下标位置向上,一点一点的建堆,
而这最后面不是叶子节点的下标位置等于 : 最后一个叶子节点的父节点
的 (n-1-1）/2 ，
其中的 (n -1)表示的是数组的最后一个数值的下标位置,
(n -1 -1) /2 通过孩子计算父节点的数组下标位置的公式
*/
for(int i = (n - 1 - 1) / 2; i >= 0; i--)
{ // 直到数组下标 0 处, i-- 向上走
AdjustDwonSmall(arr, n, i); // 向下调整算法, 从后向上建堆
}
/* 堆排序: 降序: 建小堆
* 小堆: 堆顶最小, 通过从数组堆尾,一步一步的和堆头的最小值交换，从而到达数组的降序的排序
*/
int end = n - 1; // 数组的最后下标位置
while (end >= 0)
{
swap(&arr[0], &arr[end]); // 尾头交换数值
AdjustDwonSmall(arr, end, 0); // 重新调整算法，更新去了最后一个数值的堆
end--; // 继续尾交换后,不再是堆的一部分了,逻辑上移除
}
}
/********************************* 堆排序, 升序 建大堆************/
/*
* 升序,为什建大堆,降序, 为什么建小堆
堆排序其实是选择排序的一种,通过堆来选数
1. 升序, 为什么,建大堆
如果是小堆,最小数在堆顶,已经被选出来了,那么要在剩下的堆数中, 再去选数,但是,剩下的树结构,因为你把堆顶去了,后面的
结构就乱了,不在是大小堆中的任意一个了,所以需要根据剩下的数值,重新建小堆,才能继续选出次小的数值,但是建堆时间复杂度是O(n-1)
那么这样不是不可以而是建堆排序就没有效率优势了,还不如直接遍历选数排序
*/
// 向下调整算法,建大堆,升序
void AdjustDwonBig(int* arr, int n, int root)
{
int parent = root; // 父节点数组下标位置
int leftChild = root * 2 + 1; // 默认是左孩子数组下标位置
/* 建大堆: 父节点大于等于左右孩子的数值, 堆顶最大
1. 当到达叶子节点, 左孩子的数组下标位置大于 数组的长度的时候, 不用再向下调整了
2. 当父节点的数组下标的数值是最大的时候,也不用再向下调整了,跳出循环
*/
while (leftChild < n)
{
// 判断左右孩子,那个大, 大得与父节点交换
/* 注意判断右孩子(leftChild +1)是否存在,防止右孩子不存在,数组越界了
* 上面循环(while (leftChild < n)) 判断了左孩子是否越界了
*/
if (leftChild +1 < n && arr[leftChild + 1] > arr[leftChild])
{
// 这里判断的是,右孩子的数值大, +1 把默认的左孩子变成右孩子的下标位置
leftChild = leftChild + 1; // 左孩子+1 变右孩子
}
// 判断是否比父节点的数值大,大和父节点交换
if (arr[leftChild] > arr[parent])
{
swap(&arr[leftChild], &arr[parent]); // 注意传地址,形参的改变影响实参
parent = leftChild; // 更新父节点,继续向下调整,以下面的小的左孩子做父节点
leftChild = parent * 2 + 1; // 更新左孩子的数组下标,继续向下调整
}
else // 当父节点已经是最大的时候,就不用再向下调整了,跳出循环
{
break;
}
}
}
// 堆排序,升序
void HeapSortAsc(int* arr, int n)
{
/*
* 实际上我们给的数组一般都不是堆,
* 所以我们需要建堆,升序建大堆，
* 从最后面不是叶子节点的位置开始调整,一步一步建大堆
* 该位置的下标等于= 数组最后一个下标位置的父节点
* (n-1-1) / 2
* n-1 是数组的最后一个下标位置
*/
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwonBig(arr, n, i);
}
// 堆排序,升序建大堆
/* 头尾交换
直到数组 下标 0 处
*/
int end = n - 1; // 数组的最后一个下标位置
while (end >= 0)
{
swap(&arr[0], &arr[end]); // 堆头尾交换,注意传地址,形参的改变影响实参
AdjustDwonBig(arr, end, 0); // 更新去了最后一个数值的堆
end--;
}
}
// 堆排序, 测试
void testHeapSort()
{
int arr[] = { 3,5,2,7,8,6,1,9,4,0 };
// 堆排序,降序
printf("堆排序:降序: ");
HeapSortDesc(arr, sizeof(arr) / sizeof(int));
playArrays(arr, sizeof(arr) / sizeof(int));
/*
* sizeof(arr) / sizeof(int) 表示计算数组的大小
* sizeof(arr) : 表示数组的大小, 单位字节
* sizeof(int): 表示数组元素类型的大小,单位字节
*/
// 堆排序,升序
printf("堆排序:升序: ");
HeapSortAsc(arr, sizeof(arr) / sizeof(int));
playArrays(arr, sizeof(arr) / sizeof(int));
}
/*************************** 直接选择排序 ********************/
// 直接选择排序,升序
void selectSortAsc(int* arr, int n)
{
int begin = 0; // 数组最开头的下标位置
int end = n - 1; // 数组最后面的下标位置
// 一头一尾, 交换
while (begin < end)
{
int min = begin; // 数组中最小值的下标位置
int max = begin; // 数组中最大值的下标位置, 默认最开始数组最大最小的数值的下标位置都是 0 ,用于比较数组的的数值
for (int i = begin; i <= end; i++) // 注意这里是 i = begin 不是 0 因为是一步一步向上走的
{
// 找到数组中最小的数值的下标位置
if (arr[min] > arr[i])
{
min = i;
}
// 找到数组中最大的数值的下标位置
if (arr[max] < arr[i])
{
max = i;
}
}
// 跳出循环,数组的最大值,最小值的下标位置都找到了,交换一头一尾
swap(&arr[min], &arr[begin]); // 最小值,放到数组最前的位置 begin
if (begin == max) // 需要修正一下 max的位置
{
max = min; // 因为当优先交换的缘故，当 begin = max 的时候,
// max 最大值的下标位置会被改变到min的位置处了,所以需要修正
}
swap(&arr[max], &arr[end]); // 最大值,放到数组最后面的位置 end
end--; // 下标前移
begin++; // 下标后移
}
}
// 直接排序,降序
void SelectSortDesc(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int max = begin; // 设置默认最大值的下标
int min = begin; // 设置默认最小值的下标位置, 无论是最大还是最小值的下标默认设置都为数组的 0 下标位置，比较好比较判断
for (int i = begin; i <= end; i++)
{
// 找到 数组中的最小值的下标位置
if (arr[min] > arr[i])
{
min = i;
}
// 找到数组中的最大值的下标位置
if (arr[max] < arr[i])
{
max = i;
}
}
// 找到其数组中的最大值和最小值跳出循环
/* 降序
把数值大的放到数组的前面
数值小的放到数组的后面
*/
swap(&arr[min], &arr[end]); // 把数值小的放到数组的后面, 注意使用传地址的方式,形参的改变影响实参
if (max == end) // 当最大值在 end 的位置的时候,会被 前面的交换改变下标位置的
{ // 改变到了min 的下标位置所以我们需要修正一下
max = min;
}
swap(&arr[max], &arr[begin]); // 把数值大的放到数组的前面,注意传地址,形参的改变影响实参
begin++; // 后移动
end--; // 前移动
}
}
// 直接选择排序,测试
void testSelectSort()
{
int arr[] = { 0,5,2,7,8,6,1,9,4,0 };
printf("直接选择排序:升序: ");
selectSortAsc(arr, sizeof(arr) / sizeof(int));
playArrays(arr, sizeof(arr) / sizeof(int));
printf("直接选择排序:降序: ");
SelectSortDesc(arr, sizeof(arr) / sizeof(int));
playArrays(arr, sizeof(arr) / sizeof(int));
}
/* 直接选择排序，是最差的排序算法, 最坏的情况, 时间复杂度为O(N*N)
* 最差的原因是: 无论是最好的情况,本身该数组就是有序的,其排序的时间复杂度还是 O(n*n)
* 就是说无论是最好的情况,还是最坏的情况时间复杂度都为O(n*n)
*/
// 堆排序,选择排序 的性能测试
void Testop()
{
srand(time(0)); // 设定时间种子
const int N = 100000; // 设置数组的大小
int* a = (int*)malloc(sizeof(int) * N); // 堆区上开辟 10w 个空间
int* b = (int*)malloc(sizeof(int) * N); // 堆区上开辟 10w 个空间
// 判断动态(堆区) 上开辟的空间是否成功
if (NULL == a || NULL == b)
{
perror("malloc error"); // 提示错误
exit(-1); // 非正常退出程序
}
for (int i = 0; i < N; i++)
{
a[i] = rand(); // 生成随机值
b[i] = a[i]; // 赋值,让两个数组中的值一样,控制变量
}
int begin1 = clock(); // 直接选择排序,运行前的时间点
selectSortAsc(a, N); // 直接选择排序,升序
int end1 = clock(); // 直接选择排序,运行结束后的时间点
int begin2 = clock(); // 堆排序,运行前的时间点
HeapSortAsc(a, N); // 堆排序,升序
int end2 = clock(); // 堆排序,运行结束后的时间点
/*
* 排序的运行时间 = （排序运行结束后的时间点 end) - (排序运行前的时间点 begin)
*/
printf("直接选择排序: ");
printf("%d\n", end1 - begin1);
printf("堆排序: ");
printf("%d\n", end2 - begin2);
}
int main()
{
// 堆排序测试
testHeapSort();
// 直接排序测试
testSelectSort();
// 直接选择排序, 堆排序的性能测试
Testop();
return 0;
}
插入排序，选择排序 ： 🔜🔜🔜 图文并茂 —— 插入排序，希尔排序_ChinaRainbowSea的博客-CSDN博客
最后:
限于自身水平，其中存在的错误，希望大家给予指教，韩信点兵——多多益善，谢谢大家，后会有期，江湖再见 !!!
