六安网站关键词排名优化地址,手机网站菜单设计模板,苏州做网站知识的分享,wordpress图片批量修改一#xff1a;基本思想
每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xff0c;直到全部待排序的数据元素排完 。 解释#xff1a;就是不断的找到最小的放在最左面#xff0c;然后缩短数组#xff0c;…
一基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 解释就是不断的找到最小的放在最左面然后缩短数组继续找最小的放在最左面最后就是一个升序数组。
二代码
单向选择排序
void SelectSort(int* a, int n)
{// 初始化begin为数组的第一个元素int begin 0;// 当begin小于n-1时循环即只要不是数组的最后一个元素就继续排序while (begin n - 1){// 假设当前begin位置的元素是最小的int mini begin;// 从begin1到数组最后一个元素之间查找真正的最小元素for (int i begin 1; i n - 1; i){// 如果找到一个比当前假设的最小元素还要小的元素更新mini的值if (a[i] a[mini]){mini i;}}// 将找到的最小元素与begin位置的元素交换Swap(a[mini], a[begin]);// 交换完成后begin位置的元素已经是正确的元素将begin向后移动一位begin;}
}
解释
1n是元素的个数n-1是元素下标的最大值beginn-1即代表begin最大能取到n-2此时数组还剩2个元素是最后一次查找再往下一个数字不用查找了所以begin n - 1 2缩短数组就是代码中的begin找到最小并且交换之后begin向后移动一位进入新一轮的查找
双向选择排序
void SelectSort2(int* a, int n)
{// 初始化begin为数组的起始位置end为数组的末尾位置int begin 0;int end n - 1;// 当begin小于end时表示数组中还有元素未排序while (begin end){// 初始化最小元素和最大元素的索引为beginint mini begin;int maxi begin;// 从begin1到end遍历数组寻找当前未排序部分的最小和最大元素for (int i begin 1; i end; i){// 如果当前元素大于已知最大元素的值更新最大元素的索引if (a[i] a[maxi]){maxi i;}// 如果当前元素小于已知最小元素的值更新最小元素的索引if (a[i] a[mini]){mini i;}}// 将找到的最小元素交换到begin位置Swap(a[mini], a[begin]);// 如果最大元素的索引刚好是begin此时begin位置的元素已经被最小元素替换了// 那么需要更新最大元素的索引为mini因为最小元素已经被交换到begin位置if (maxi begin){maxi mini;}// 将找到的最大元素交换到end位置Swap(a[maxi], a[end]);// 缩小未排序部分的范围end向左移动一位begin向右移动一位end--;begin;}
}
解释
1和第一种相比区别在于它每次遍历数组的时候不仅找最小还要找最大然后再通过交换每次的遍历能确定两个元素的位置
2在交换时我们第一步Swap(a[mini], a[begin]);将找到的最小元素交换到begin位置但是如果最大元素的索引刚好是begin此时begin位置的元素已经被最小元素替换了那么需要更新最大元素的索引为mini因为最小元素已经被交换到begin位置再将找到的最大元素交换到end位置才是正确的交换。
图示如下 三代码运行结果
对同一个十万个整形的数组进行选择排序 可以看出两者相差不大毕竟都是同一个量级的时间复杂度。 四复杂度讲解
时间复杂度
选择排序的时间复杂度在最好、最坏和平均情况下都是O(n^2)
解释
第一轮需要比较n-1次对于n个元素的数组。第二轮需要比较n-2次。…最后一轮需要比较1次。 因此总的比较次数是 (n-1) (n-2) … 1 n(n-1)/2大O表示为O(n^2)。
空间复杂度
选择排序的空间复杂度是O(1)。
选择排序是在原地进行排序的不需要额外的存储空间来存储数据。
五两种选择排序的对比
单向选择排序和双向选择排序的时间复杂度在理论上是相同的都是O(n^2)。这是因为两种排序算法都需要遍历整个未排序的部分来找到最小或最大的元素并且在每一轮排序中都需要进行一定数量的比较。
具体来说 单向选择排序在每一轮排序中算法会找到未排序部分的最小或最大元素并将其放到已排序部分的末尾。每轮排序需要进行n-i次比较其中i是当前轮次的索引从0开始。因此总的比较次数是 (n-1) (n-2) … 1 n(n-1)/2这是O(n^2)的时间复杂度。 双向选择排序在每一轮排序中算法会同时找到未排序部分的最小和最大元素并将它们分别放到已排序部分的末尾和开始。尽管每一轮可以处理两个元素但每轮排序仍然需要遍历整个未排序的部分因此每轮排序的比较次数与单向选择排序相似。总的比较次数同样是O(n^2)。
虽然双向选择排序在每一轮可以减少交换次数可能只需要两次交换而单向选择排序可能需要一次但是比较次数并没有减少。因此两种算法在时间复杂度上是等价的。
需要注意的是尽管时间复杂度相同双向选择排序在实际执行中可能会有更好的性能因为它减少了交换次数而交换操作通常比比较操作更耗时。然而这种性能提升通常不足以改变算法的时间复杂度类别。
六代码分享
#includestdio.h
#includetime.h
#includestdlib.h
#includeassert.h
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void SelectSort(int* a, int n)
{// 初始化begin为数组的第一个元素int begin 0;// 当begin小于n-1时循环即只要不是数组的最后一个元素就继续排序while (begin n - 1){// 假设当前begin位置的元素是最小的int mini begin;// 从begin1到数组最后一个元素之间查找真正的最小元素for (int i begin 1; i n - 1; i){// 如果找到一个比当前假设的最小元素还要小的元素更新mini的值if (a[i] a[mini]){mini i;}}// 将找到的最小元素与begin位置的元素交换Swap(a[mini], a[begin]);// 交换完成后begin位置的元素已经是正确的元素将begin向后移动一位begin;}
}
void SelectSort2(int* a, int n)
{// 初始化begin为数组的起始位置end为数组的末尾位置int begin 0;int end n - 1;// 当begin小于end时表示数组中还有元素未排序while (begin end){// 初始化最小元素和最大元素的索引为beginint mini begin;int maxi begin;// 从begin1到end遍历数组寻找当前未排序部分的最小和最大元素for (int i begin 1; i end; i){// 如果当前元素大于已知最大元素的值更新最大元素的索引if (a[i] a[maxi]){maxi i;}// 如果当前元素小于已知最小元素的值更新最小元素的索引if (a[i] a[mini]){mini i;}}// 将找到的最小元素交换到begin位置Swap(a[mini], a[begin]);// 如果最大元素的索引刚好是begin此时begin位置的元素已经被最小元素替换了// 那么需要更新最大元素的索引为mini因为最小元素已经被交换到begin位置if (maxi begin){maxi mini;}// 将找到的最大元素交换到end位置Swap(a[maxi], a[end]);// 缩小未排序部分的范围end向左移动一位begin向右移动一位end--;begin;}
}
void TestOP()
{//生成N个随机数srand(time(0));int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);assert(a1);assert(a2);for (int i 0; i N - 1; i){a1[i] rand();a2[i] a1[i];}//clock函数计算排序函数运行的时间int begin1 clock();SelectSort(a1, N);int end1 clock();//clock函数计算排序函数运行的时间int begin2 clock();SelectSort2(a2, N);int end2 clock();printf(SelectSort:%d\n, end1 - begin1);printf(SelectSort2:%d\n, end2 - begin2);//释放空间free(a1);//释放空间free(a2);}
int main()
{//单向选择排序TestOP();return 0;
}
