【java基础】选择排序算法原理+实现 川长思鸟来 2022-08-23 05:42 142阅读 0赞 # 思想: # 一次遍历,只需一次交换; 选择排序,每次选最小,放在已排序队列末尾,依次进行,直到全部排序完成. # 执行: # ![Center][] (1)从待排序序列中,找到最小的元素; (2)如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换; (3)从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。 [1, 54, 6, 3, 78, 34, 12, 45] ---第1轮 ---------第1次 1 54 6 3 78 34 12 45 ---------第2次 1 54 6 3 78 34 12 45 ---------第3次 1 54 6 3 78 34 12 45 ---------第4次 1 54 6 3 78 34 12 45 ---------第5次 1 54 6 3 78 34 12 45 ---------第6次 1 54 6 3 78 34 12 45 ---------第7次 1 54 6 3 78 34 12 45 ---第2轮 ---------第2次 1 3 6 54 78 34 12 45 ---------第3次 1 3 6 54 78 34 12 45 ---------第4次 1 3 6 54 78 34 12 45 ---------第5次 1 3 6 54 78 34 12 45 ---------第6次 1 3 6 54 78 34 12 45 ---------第7次 1 3 6 54 78 34 12 45 ---第3轮 ---------第3次 1 3 6 54 78 34 12 45 ---------第4次 1 3 6 54 78 34 12 45 ---------第5次 1 3 6 54 78 34 12 45 ---------第6次 1 3 6 54 78 34 12 45 ---------第7次 1 3 6 54 78 34 12 45 ---第4轮 ---------第4次 1 3 6 12 78 34 54 45 ---------第5次 1 3 6 12 78 34 54 45 ---------第6次 1 3 6 12 78 34 54 45 ---------第7次 1 3 6 12 78 34 54 45 ---第5轮 ---------第5次 1 3 6 12 34 78 54 45 ---------第6次 1 3 6 12 34 78 54 45 ---------第7次 1 3 6 12 34 78 54 45 ---第6轮 ---------第6次 1 3 6 12 34 45 54 78 ---------第7次 1 3 6 12 34 45 54 78 ---第7轮 ---------第7次 1 3 6 12 34 45 54 78 1 3 6 12 34 45 54 78 # 分析: # 如下代码可看出,选择排序的时间复杂度是O(n\*n);由于此算法利用了一个临时空间,当做中转位置来放置每次的最小值,所以,它的空间复杂度是O(1). # 实现: # import java.util.Arrays; public class selectSort { public static void main(String[] args){ int a[]={1,54,6,3,78,34,12,45}; //输出定义的数组 System.out.println(Arrays.toString(a)); //可以理解成这是一个每次比较的标志位 int position=0; for(int i=1;i<a.length;i++){ System.out.println("---第"+i+"轮 "); position=i; //定义一个临时存放数值 int temp=a[i]; //内层循环---循环找出当前最小的,和标志位的数字比较,若小则交换位置 for(int j=i;j<a.length;j++){ if(a[j]<temp){ temp=a[j]; position=j; } System.out.println("---------第"+j+"次 "); //依次循环输出当前数组中的数字 for (int l = 0; l < a.length; l++) { System.out.print(a[l] + " "); } System.out.println(" "); } //若本轮中数字不用交换位置,则保持当前 a[position]=a[i]; a[i]=temp; } } } [Center]: /images/20220721/5edc754233ac40dc825f575a1f2bee27.png
还没有评论,来说两句吧...