首页 > 代码库 > 排序算法6--选择排序--简单选择排序
排序算法6--选择排序--简单选择排序
简单选择排序
简单选择排序属于选择排序, 选择排序的思想是:每一趟从待排序的记录中选出关键字最小的记录,按顺序放在以排序的记录序列的后面,知道全部排完为止。
1.简单选择排序法是每次循环找出最值,循环结束后将最值调整到合适位置,交换的次数少。
每次找出当前无序队列中的最小的元素与第一个交换位置,再选择第二小的与第二个交换位置
原始队列: 3 5 6 2 4 1(最小元素1与3交换)
第一步: 1 5 6 2 4 3 (当前最小元素2与5交换)
第二步: 1 2 6 5 4 3 (当前最小元素3与6交换)
第三步: 1 2 3 5 4 6 (当前最小元素4与5交换)
第四步: 1 2 3 4 5 6
第五步: 1 2 3 4 5 6
第六步: 1 2 3 4 5 6
2.时间复杂度
最好情况(正序)不移动
最坏情况(逆序)移动3(n-1)次
平均时间复杂度O(n*n)
空间复杂度O(1)
具体时间复杂度等分析,请参考:http://www.cnblogs.com/zhangxue521/p/6748085.html
3.算法特点
①稳定排序
②可用于链式存储结构
③移动记录次数较少,当每一记录占用空间较多时,此方法比直接插入排序快
java实现:
1 package 平时常用; 2 3 import java.util.Scanner; 4 5 public class _2简单选择排序 { 6 public static void main(String[] args) { 7 int a[] = new int[6]; 8 Scanner scanner = new Scanner(System.in); 9 for (int i = 0; i < a.length; i++) {10 a[i] = scanner.nextInt();11 }12 for (int i = 0; i < a.length; i++) {13 int min = i;14 // 循环找当前队列中的最小的数字,将min标志赋予它15 for (int j =i+1; j < a.length; j++) {16 if ( a[j]<a[min] ) {17 min = j;18 }19 }20 //交换最小值到当前无序队列的最前面21 if (min!=i) {22 int temp = a[i];23 a[i] = a[min];24 a[min] = temp;25 }26 for (int m : a) {27 System.out.print(m+" ");28 }29 System.out.println();30 }31 }32 }
js实现:
1 function jiandanSort(a){ 2 var i,j,temp,min; 3 for (i=0;i<a.length;i++) { 4 min = i; 5 //循环找到当前队列的最小值 6 for (j = i+1;j<a.length;j++) { 7 if(a[j]<a[min]) 8 min = j; 9 }10 //将最小值交换到当前无序队列的最前面11 if(min!=i){12 temp = a[i];13 a[i] = a[min];14 a[min] = temp;15 }16 }17 }18 var a = new Array(7,2,6,5,1,4,3);19 jiandanSort(a);20 document.write("_6简单选择排序:"+a +"<br />");
排序算法6--选择排序--简单选择排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。