常用排序算法二-一一网

五、直接选择排序

　　1、基本介绍

　　选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从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次，得到一个按排序码从小到大排列的有序序列。

　　2、代码实现

 1  //O(n2)
 2     public static void selectSort(int[] arr){
 3         for (int i = 0; i < arr.length-1; i++) {
 4             //假定最小值为i
 5             int minIndex = i;
 6             //j从i+1开始
 7             for (int j = i+1; j <arr.length ; j++) {
 8                 //如果假定的最小值大于后面一个元素即arr[j],则吧minIndex指向arr[j]
 9                 //否则不进入if判断
10                 if(arr[minIndex]>arr[j]){
11                     minIndex = j;
12                 }
13             }
14             //如果minIndex没有变化，即，minIndex就是arr[i]，不需交换
15             if(minIndex!=i) {
16                 int tmp = arr[i];
17                 arr[i] = arr[minIndex];
18                 arr[minIndex] = tmp;
19             }
20         }
21     }