便利的邯郸网站建设,重庆公司网站建设,组件化网站建设,龙岗大运做网站的公司目录
选择排序
SelectSort直接选择排序
整体思路
图解分析
代码实现
时间复杂度 选择排序 基本思想#xff1a; 每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xff0c;直到全部待排…目录
选择排序
SelectSort直接选择排序
整体思路
图解分析
代码实现
时间复杂度 选择排序 基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 直接选择排序是暴力选数值。堆排序是在堆的结构上选数值。 SelectSort直接选择排序 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换。在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素。优化遍历一遍同时选取最小的和最大的值同时放在第一位和最后一位存在一个坑 直接选择排序的特性总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定 整体思路 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换。在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素。优化遍历一遍同时选取最小的和最大的值同时放在第一位和最后一位存在一个坑优化本来是一次选出最小的优化之后一次选出最小的和最大的。在a[0]~a[n-1]遍历中选出最大的数和最小的数的下标最大的数的下标maxi 最小的数的下标mini最大的数的位置的下标begin 0最小的数的位置的下标end n-1选出元素下标和对应位置的下标的元素交换不是覆盖❗重复上诉过程然后begin-- / end 直到它们相遇begin end )注意❗最大值元素的下标maxi可能与最小值的元素的位置begin下标重叠导致交换完最小值a[begin]和a[mini]交换之后的那个位置的元素不是最大值maxi而是最小值mini。❗注意这里交换的是数值下标没有交换也就是说交换完之后maximini任然指向原来的位置 图解分析 大家可以自己尝试画优化版的选择排序 243265189100 每次遍历的i的范围[beginend]begin和end是变化的最大值元素的下标maxi可能与最小值的元素的位置begin下标重叠❗注意这里交换的是数值下标没有交换也就是说交换完之后maximini任然指向原来的位置 代码实现
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;int maxi begin;int mini begin;while (begin end){//遍历区间在[begin,end]for (int i begin; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}///不换}Swap(a[mini], a[begin]);if (a[maxi] a[begin]){maxi mini;}Swap(a[maxi], a[end]);begin;end--;}
} 时间复杂度 时间复杂度ON^2) 等差数列 最后会总结稳定性和各个排序效率比较数据量不同各个排序相对效率就是不同不能确定 感谢大家的阅读若有错误和不足欢迎指正。下篇堆排序回顾。
