选择排序(Select Sort)

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

基本思路

第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换， 第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换， 第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换， 第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换， 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换， 总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

分析

原始数组：101，34，119，1 第一轮排序 : 1, 34, 119, 101 第二轮排序 : 1, 34, 119, 101 第三轮排序 : 1, 34, 101, 119

说明

1.选择排序一共有 数组大小 - 1 轮排序 2. 每1轮排序，又是一个循环, 循环的规则(代码) 2.1先假定当前这个数是最小数 2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标 2.3 当遍历到数组的最后时，就得到本轮最小数和下标 2.4 进行交换交换 [代码中再继续说 ]

代码

public class SelectSort { public static void main(String[] args) { // int arr[] = {102, 119, 34, 1}; // selectSort(arr); // System.out.println(Arrays.toString(arr)); //测试时间 int arr[]=new int [80000]; for (int i = 0; i < 80000; i++) { arr[i]=(int)(Math.random()*800000); } long startMillis=System.currentTimeMillis(); selectSort(arr); long endMillis = System.currentTimeMillis(); System.out.println("选择排序耗时："+(endMillis-startMillis)+"ms"); } public static void selectSort(int arr[]) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { min = arr[j]; //重置min minIndex = j; //重置minIndex } } //将最小值，放在arr【0】，即交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } // System.out.println("~~~第" + (i + 1) + "轮后~~~"); // System.out.println(Arrays.toString(arr)); } } }

测试八万个数据耗时：3236ms