建设工程教育网官网下载,手机网站优化指南,邯郸百度网站建设,logo生成器app选择排序 与 堆排序 选择排序 选择排序 与 堆排序1 选择排序1.1 选择排序原理1.2 排序步骤1.3 代码实现 2 堆排序2.1 堆排序原理2.1.1 大堆与小堆2.1.2 向上调整算法2.1.3 向下调整算法 2.2 排序步骤2.3 代码实现 3 时间复杂度分析 Thanks♪(#xff65;ω#xff65;)#…选择排序 与 堆排序 选择排序 选择排序 与 堆排序1 选择排序1.1 选择排序原理1.2 排序步骤1.3 代码实现 2 堆排序2.1 堆排序原理2.1.1 大堆与小堆2.1.2 向上调整算法2.1.3 向下调整算法 2.2 排序步骤2.3 代码实现 3 时间复杂度分析 Thanks♪(ω)下一篇文章见 1 选择排序
1.1 选择排序原理
选择排序可以用扑克牌理解眼睛看一遍所有牌选择最小的放在最左边。然后略过刚才排完的那张继续进行至扑克牌有序。这样一次一次的挑选思路很顺畅。总结为 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
1.2 排序步骤
从头开始遍历数组设置mini指向最小值下标先指向首元素。遇到比a[mini]小的值mini改变为新下标。直到遍历到结尾。将数组首元素与mini指代元素交换位置。从排好序的下一个元素开始重复 1-3 步骤。直到排序完成。
1.3 代码实现
void SelectSort(int* a, int n) {int begin 0;//无序部分开头int mini 0;//先设置mini指向开头//直到begin n ,都有序。while (beginn) {//从无序部分开始选择最小值。for (int i begin; i n; i) {if (a[i] a[mini]) //如果小则下标更新。mini i;}//将选择出来的最小值放置到无序部分开头。swap(a, begin, mini);begin;//begin向后推进mini begin;//mini更新}
}排序功能实现效果非常棒 直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
2 堆排序
2.1 堆排序原理
堆排序是一种特殊的选择排序堆排序以二叉树为基础。选择两个子元素其一然后逐层上升或下沉直到有序。在认识理解堆排序之前我们需要了解如何建堆。这里我们由于是学习堆排序所以下面我只介绍堆的大小堆建立向上调整算法向下调整算法。其余堆相关知识会在另一篇文章详细介绍。
2.1.1 大堆与小堆
首先堆 是一种特殊的树满足以下条件即为堆是二叉树的顺序结构。 二叉树内容见二叉树解释 根据二叉树的知识堆一定是完全二叉树除了最后一层其他层的节点个数都是满的最后一层的节点都集中在左部连续位置 堆分为大小堆 即 堆中每一个节点的值都必须大于等于或小于等于其左右子节点的值 每个节点的值都大于等于其子树节点的堆叫“大堆“根是所有数据的最大值 每个节点的值都小于等于其子树节点的堆叫“小堆“根是所有数据的最小值
2.1.2 向上调整算法
我们如何把基本的数组变成大堆和小堆呢这里就需要向上调整算法。 向上调整顾名思义就是从尾部开始一层一层向上调整。
以建大堆为例
从尾节点开始如果该孩子节点大于父母节点则向上调整上浮。直到调整到合适的位置。尾节点向前推移继续重复 1 - 2 步骤。直到遍历所有元素完成建堆。
void adjustup(int* a, int child) ;
int main(){
//...for (int i n - 1; i 0; i--) {adjustup(a, i);//逐个遍历}
//...
}
//建堆void adjustup(int* a, int child) {int parent (child - 1) / 2;//根据二叉树知识取父母节点while (child 0) {if (a[child] a[parent]) {swap(a, child, parent);//如果该孩子节点大于父母节点则向上调整上浮}child parent;//孩子节点迭代parent (child - 1) / 2;//父母节点迭代}}这样就建立了大堆。小堆原理相同只需更改大于号和小于号。
2.1.3 向下调整算法
建立好堆之后如何进行排序呢?这时就需要向下调整算法。首先我们要有一个共识 排升序建大堆排倒序建小堆。 之所以这样是因为向下调整算法的缘故下面我们来看向下调整算法之后解释原因。 以排升序为例
首先头元素与尾元素交换位置。然后从头开始向下调整如果父母节点大于孩子节点中较大的则交换。调整完成后尾向前推进。继续重复 1 - 2 步骤。直到遍历所有元素。
void adjustdown(int* a, int parent,int size);
int main(){
//...int end n - 1;while (end 0) {swap(a, end, 0);adjustdown(a,0,end);end--;}
//...
}
void adjustdown(int* a, int parent,int size) {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, parent);}parent child;child parent * 2 1;}}这样遍历一遍向下调整就可以完成排序。我们理解向下调整算法之后就可以发现 **排升序建大堆排倒序建小堆。**是非常巧妙的 以排升序为例每次放在交换到首元素 的都是最小值最大值然后向下调整把它放到该放在的位置上。
2.2 排序步骤
我们理解上述两种算法之后就可以非常顺畅理解堆排序。
向上调整建堆向下调整排序 理解向上调整算法和向下调整算法之后堆排序就迎刃而解。
2.3 代码实现
void adjustup(int* a, int child) {int parent (child - 1) / 2;while (child 0) {if (a[child] a[parent]) {swap(a, child, parent);}child parent;parent (child - 1) / 2;}}void adjustdown(int* a, int parent,int size) {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, parent);}parent child;child parent * 2 1;}}
void HeapSort(int* a, int n) {assert(a);for (int i n - 1; i 0; i--) {adjustup(a, i);//逐个遍历}int end n - 1;while (end 0) {swap(a, end, 0);adjustdown(a,0,end);end--;}
}这里我们是可以进一步优化的因为向上调整算法可以有向下调整算法来代替。 算法优化就交给你完成了。
3 时间复杂度分析
让我们和之前的排序算法来比较一下。依然是10万组数据让我们看一下运行时间。以冒泡排序为对照
显然选择排序和插入排序是一个级别堆排序和希尔排序都非常快速。 我们再来比较一下希尔排序与堆排序。100万组数据 这里希尔貌似更快但其实希尔排序与堆排序是一个量级甚至在更多数据下堆排序会更优。
Thanks♪(ω)
下一篇文章见
