优秀个人博客网站,成都seo论坛,小程序进入公众号,wordpress菜单选项1基本思想#xff1a;
每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xff0c;直到全部待排序的 数据元素排完 。
2 直接选择排序: 在元素集合 array[i]--array[n-1] 中选择关键码最大 ( 小 ) 的数据元素…1基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的 数据元素排完 。
2 直接选择排序: 在元素集合 array[i]--array[n-1] 中选择关键码最大 ( 小 ) 的数据元素。 若它不是这组元素中的最后一个 ( 第一个 ) 元素则将它与这组元素中的最后一个第一个元素交换。 在剩余的 array[i]--array[n-2] array[i1]--array[n-1] 集合中重复上述步骤直到集合剩余 1 个元素。 选择排序的单趟就是找出最大的值的下标maxi和最小值的下标mini然后将最小值放在最左边最大值放在最右边。首先写一个单趟maxi和mini都在同一个位置(最左边)然后写一个for循环下标i用来遍历数组i的起始位置是begin1结束条件是iend进入循环开始找最大值和最小值的下标循环结束意味着maxi和mini已经到了相应的位置就可以开始交换值了交换完最小值后要注意一下如果maxi一直是begin这个位置那么就已经被换走了换到了a[mini]这个位置所以要修正一下将maximini再交换最大值。那么单趟走完之后beginend--每次进入循环maxi和mini都在begin这个位置所以最外层套一个while循环结束条件是beginend。 //选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){//更新最大/小值的的下标if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
} 直接选择排序的特性总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性不稳定 3 堆排序 堆排序 (Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 堆排序在前面的一篇文章中有详细介绍 http://t.csdnimg.cn/S4Ysohttp://t.csdnimg.cn/S4Yso 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(1) 4. 稳定性不稳定 今天的分享到这里就结束了感谢大家的阅读
