首页 > 代码库 > 选择排序
选择排序
1.算法描述
2.实例
使用选择排序法将下面数列按升序排序:
8 3 4 2 6 5
第一次在六个数字中找到最小的数字2,和数列的第一个数字交换位置,数列如下:
2 3 4 8 6 5
第二次在剩下的五个数字中找到最小的数字3,和数列的第二个数字交换位置,因为3本来的位置就是数列的第二个数字,数列顺序没有发生变化:
2 3 4 8 6 5
第三次在剩余的四个数字中找最小的数字4,和第二次情况一样,数列位置依然没有发生变化,如下:
2 3 4 8 6 5
第四次在剩余的三个数字中找最小的数字5,和数列的第四个数字交换位置,数列如下:
2 3 4 5 6 8
第五次在剩余的两个数字中找最小的数字6,和第二、三次情况一样,数列位置依然没有发生变化,如下:
2 3 4 5 6 8
第六次在剩余的一个数字中找最小的数字8,和第五次情况一样,数列如下:
2 3 4 5 6 8
最终排序后的数列也就出来了:
2 3 4 5 6 8
3.代码
void selection_sort::selection_sort_with_array(int nums[],int nums_count) { if(nums == nullptr || nums_count==0) return; int a = 0; for(unsigned int i = 0; i< nums_count; i++) { a = i; for(unsigned int j = i+1; j< nums_count; j++) { if(nums[a]>nums[j]) a = j; } if(a != i) { int temp = nums[a]; nums[a] = nums[i]; nums[i] = temp; } } }
4.算法分析
在“3.代码“中我们可以看出,选择排序算法的基本操作就是比较和替换,那我们来计算一下它的时间复杂度:
从上面的内容中我们可以看出,比较的次数只和数组中数字的个数相关,假设一个长度为n的数组,分析如下:
选择第一个最小数,需要比较n-1次
选择第二个最小数,需要比较n-2次
选择第三个最小数,需要比较n-3次
............... ........ ......... ....
选择地n个最小数,需要比较0次
根据上面的分析,对一个长度为n的数组进行排序,比较次数为:
C(n)=(n-1)+(n-2)+(n-3)+....+0 = n*(n-1)/2;(等差公式:Sn=n*a1+n*(n-1)*d/2)
在最坏情况下,替换次数为:n-1
因此选择排序的时间复杂度为:O(n^2);
选择排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。