本文共 1649 字,大约阅读时间需要 5 分钟。
算法描述:
举例
先说看每步的状态变化,后边介绍细节,现有无序数组[6 2 4 1 5 9]
第一趟找到最小数1,放到最前边(与首位数字交换)
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位
交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换
第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置
交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
交换后:| 1 | 2 | 4 | 5 | 6 | 9 |
第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换
排序完毕输出正确结果[1 2 4 5 6 9]
第一趟找到最小数1的细节
当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |
先把6取出来,让它扮演最小数
当前最小数6与其它数一一进行比较,发现更小数就交换角色
当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较
当前最小数2与4比较,不动
当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较
当前最小数1与5比较,不动
当前最小数1与9比较,不动,到达末尾
当前最小数1与当前首位数字进行位置交换,如下所示
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
完成一趟排序,其余步骤类似
package sort;public class 选择排序 { /** * @param args */ public static void main(String[] args) { int []arr={ 101,34,119,1}; selectSort(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } public static void selectSort(int[] arr) { for (int i = 0; i < arr.length-1; i++) { //此时的i < arr.length-1;与i < arr.length无大区别,当循环三次时,最后一个数自然出现 int minIndex=i; int min=arr[i]; for (int j = i+1; j < arr.length; j++) { //此时的j=i+1 与j=i没有大区别,第一个是假定的第一位最小值 不与本身比较;第二个 是与本身比较 if(min>arr[j]){ min=arr[j]; minIndex=j; } } if(minIndex !=i){ /*arr[minIndex]=arr[i]; arr[i]=min; */ int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } }}
转载地址:http://pothn.baihongyu.com/