网站做虚假广告,注册app,网站防止恶意注册,wordpress首页调用#x1f4f7; 江池俊#xff1a; 个人主页 #x1f525;个人专栏#xff1a; ✅数据结构冒险记 ✅C语言进阶之路 #x1f305; 有航道的人#xff0c;再渺小也不会迷途。 文章目录 一、选择排序1.1 基本思想1.2 算法步骤 动图演示1.3 代码实现1.4 选择排序特性总结 二… 江池俊 个人主页 个人专栏 ✅数据结构冒险记 ✅C语言进阶之路 有航道的人再渺小也不会迷途。 文章目录 一、选择排序1.1 基本思想1.2 算法步骤 动图演示1.3 代码实现1.4 选择排序特性总结 二、堆排序2.1 堆排序概念2.2 算法步骤 动图演示2.3 代码实现2.4 堆排序特性总结 一、选择排序
1.1 基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
1.2 算法步骤 动图演示
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余 1 个元素 1.3 代码实现
这里我们的代码可以稍作优化在每次选数的时候一次性选出最大和最小的 数然后依次与数组最后一个和第一个数进行交换。
void Swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}// 选择排序
// 时间复杂度O(N^2)
// 最好的情况下O(N^2)
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin, maxi begin;for (int i 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}1.4 选择排序特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 二、堆排序
堆排序传送门二叉树堆的应用实例分析堆排序 | TOP-K问题 虽然上面已经讲解过堆排序但在此我们最好还是继续回顾一下堆排序的算法思想。 2.1 堆排序概念
堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法
大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列
2.2 算法步骤 动图演示
创建一个堆 H[0……n-1]建议使用向下调整建堆把堆首最大值和堆尾互换把堆的尺寸缩小 1即确定最后一个数的位置并调用 向下调整算法目的是把新的数组顶端数据调整到相应位置重复步骤 2直到堆的尺寸为 1。 2.3 代码实现
以下代码以升序排序为例降序排序类似。 注意建堆时使用向下调整法要从倒数第一个非叶子节点即最后一个叶子节点的父节点开始。
// 向下调整
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果假设错了更新一下if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 堆排序 --- 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n,i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}2.4 堆排序特性总结
堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
