选择排序也是十大排序算法中的一种，他是将整个数组从头到尾全部扫描一遍，然后选择最小的与第一位进行交换，接着再在剩下的元素中进行扫描，直到扫描完毕，最终，得到一个有序数列。这是一种思路非常简单的排序算法。我们先简单的实现一下，代码如下：
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int n = arr.length - 1;// 经过n-1次提取最小最大值 long startTime = System.nanoTime(); // 获取开始时间 for (int i = 0; i < arr.length - 1; i++) { int min = i; for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; } } if (min != i) { int tmp = arr[min]; arr[min] = arr[i]; arr[i] = tmp; } } long endTime = System.nanoTime(); // 获取结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); }
打印结果如下：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：3100ns
最基本的选择排序是一次将一个元素进行位置的确定，那么我们可不可以一次确定两个元素的位置呢？
优化代码如下：
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; long startTime = System.nanoTime(); // 获取开始时间 // 最小值下标 int min = 0; // 最大值下标 int max = 0; int left = 0; int right = arr.length - 1; int j = 0; // 循环size-1次 while (left < right) { max = left; min = right; // 确定最大值下标以及最小值下标 for (j = left; j <= right; j++) { if (arr[j] > arr[max]) { max = j; } if (arr[j] < arr[min]) { min = j; } } // 将最大值插到最后 if (max != right) { int tmp = arr[max]; arr[max] = arr[right]; arr[right] = tmp; } // 防止minpos在最大值要插入的位置 if (min == right) { min = max; } // 将最小值插到最前面 if (min != left) { int tmp = arr[min]; arr[minpos] = arr[left]; arr[left] = tmp; } left++; right--; } long endTime = System.nanoTime(); // 获取结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); }
打印结果如下：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：2600ns
有朋友要问了，为什么要加上这段代码呢：
if (min == right) { min = max; }
比如数组{ 1, 3, 4, 2, 6, 7, 8, 0, 5 };max=0，min=8;
max!=8,交换0和8，[0, 1, 2, 3, 4, 5, 6, 7, 8]但是max依旧是0，minpos依旧是8，min!=0,又再次交换0和8.
所以为防止min在最大值要插入的位置，要加上上面这块代码。
