合肥网站关键词优化公司,网站建设都讲哪些内容,网站运营实例,注册公司流程和费用公司注册三、选择排序
1.简介 选择排序主要采取的排序策略就是选择#xff0c;在拿到待排序数组后#xff0c;程序会一遍遍地遍历未排序部分数组#xff0c;在每一次的遍历过程中会找到最小的元素#xff0c;并在遍历完成后换到未排序数组部分的最左侧。如此循环往复#xff0c;每…三、选择排序
1.简介 选择排序主要采取的排序策略就是选择在拿到待排序数组后程序会一遍遍地遍历未排序部分数组在每一次的遍历过程中会找到最小的元素并在遍历完成后换到未排序数组部分的最左侧。如此循环往复每一次遍历选出一个最小的数据进行排序最后达到整个数组有序。 选择排序思想方法很简单就是比较找到最小然后交换一次排好一个元素。我们也可以将选择排序做一些优化比如每次选出一个最大的和一个最小的分别排在左端和右端这样排序是从两端同时开始效率加倍。本文的选择排序就采取这种方法一次遍历选出最大值和最小值。
2.思路与代码 在写选择排序的时候我们同样试着将单步的排序写出来再加上循环生成最后的选择排序。 假设此时区间[begin,end]需要排序那么我们就需要对该区间进行遍历找到最大值与最小值的下标因为数组交换需要通过下标实现。我们可以认为最小值和最大值下标分别为begin和end当找到更小或更大的元素时修改变量赋值即可。在遍历结束后将最小值与下标为begin的值交换将最大值与下标为end的值交换。 注意此处可能存在如下情况 发生这种错误是因为最大值落在了begin位置导致最小值交换之后maxi未进行更新使得maxi指向的位置不再是最大值而变成了新换过来的最小值。解决这个问题并不难加个判断即可。于是我们可以得到单步排序代码。 int begin,end;int maxi end, mini begin;for (int i begin; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}swap(a[mini], a[begin]);if (maxi begin){maxi mini;}swap(a[maxi], a[end]); 有现在的基础再写出选择排序就不是什么难事了。我们只需要让begin与end分别从头和尾开始每次排序后begin自增、end自减即可。
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int maxi end, mini begin;for (int i begin; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}swap(a[mini], a[begin]);if (maxi begin){maxi mini;}swap(a[maxi], a[end]);begin;end--;}
}
3.复杂度与稳定性分析
1时间复杂度 选择排序的时间复杂度不难分析无论数组的情况都需要从头到尾慢慢遍历是典型的等差数列所以其时间复杂度是。
2空间复杂度 选择排序并未用到多余额外的空间所以空间复杂度是。
3稳定性 选择排序是不稳定的。 选择排序直观想象好像可以控制当a[i] a[mini]时不改变mini就可以成为稳定的。但是要敏锐地捕捉到其存在数据交换的情况从而是有可能打乱相对顺序的。如 因而我们可以认为选择排序是不稳定的。
