本文共 2919 字，大约阅读时间需要 9 分钟。
和冒泡排序一样，选择排序也是蛮力法的一种实际应用。
选择排序的思想，就是首先扫描整个数组，找到最小的元素，然后和第一个元素进行交换，如此一来就等同于将最小的元素放到它在有序表中最终的位置上。然后从第二个元素开始扫描整个表，找到剩余n-1个元素中最小的元素，与第二个元素交换位置。以此类推，在执行n-1遍之后，这个数组就自然有序了。（当然每次找最大的元素，与最后一个元素交换也是可行的）
先用一个具体的场景来体会一下选择排序的过程。
场景：
现有一个无序数组，共7个数：89 45 68 90 29 34 17。
使用选择排序对这个序列进行升序排序。
基础选择排序实现过程：
89 45 68 90 29 34 17；
17 45 68 90 29 34 89 ;
17 29 68 90 45 34 89；
17 29 34 90 45 68 89；
17 29 34 45 90 68 89；
17 29 34 45 68 90 89；
17 29 34 45 68 89 90 ;
可以很明显的发现，选择排序有一个最明显的优于冒泡排序的地方：数据交换的次数。在选择排序中，一共最多产生n-1次交换（有时当剩余数组第一个值就是最小值的时候甚至不需要进行交换），虽然选择排序的时间复杂度也是O(n^2)。另外顺便说一句，选择排序的空间复杂度也是O(1)。
附上基础选择排序的代码：
1 public static void basal(int[] array) { 2 if (array == null || array.length < 2) { 3 return; 4 } 5 // 最小元素坐标 6 int minIndex; 7 for (int i = 0; i < array.length; i++) { 8 // 每次循环开始，重置坐标 9 minIndex = i;10 // 前i个已经有序11 // 内循环的任务是在[i,array.length-1]的区间中找出最小的元素的位置，和第i项交换12 for (int j = i; j < array.length; j++) {13 if (array[j] < array[minIndex]) {14 minIndex = j;15 }16 }17 // 判断第一个是不是最小值，是的话可以不用交换18 if (i != minIndex) {19 swap(i, minIndex, array);20 }21 }22 }
选择排序有一个很重要的特性不能忽视——它是一种不稳定排序。我们假定一个数组：[5,5,6,1,8]，可以很清晰的发现，在选择排序结束之后，两个5并不能保持原来的顺序。
既然选择排序也是蛮力法，那么也可以尝试一下去优化它，优化的思路很简单。每一次外循环的遍历，只用打擂台法，去找一个最小值是不是太过浪费了一点？可以一次性地找到最大值和最小值，分别和头、尾两个元素进行交换。这样一来外循环只要执行原来一半的循环次数就可以了。但是需要注意一点：每次循环要进行2次交换，第一次最小值交换结束之后，在进行最大值交换的时候要先判断，最大值是不是在第一个位置，在第一次最小值交换的时候已经换到了后面？
附上优化选择排序的代码：
1 public static void optimized(int[] array) { 2 if (array == null || array.length < 2) { 3 return; 4 } 5 // 一次遍历，找出最大和最小两个值 6 int minIndex; 7 int maxIndex; 8 // 外循环遍历至一半就结束 9 // 如果完整遍历，整个数组会变成倒序排列10 for (int i = 0; i < array.length / 2; i++) {11 minIndex = i;12 maxIndex = i;13 // 内循环呈从两边缩进状14 for (int j = i; j < array.length - i; j++) {15 if (array[j] < array[minIndex]) {16 minIndex = j;17 }18 if (array[j] > array[maxIndex]) {19 maxIndex = j;20 }21 }22 if (i != minIndex) {23 swap(i, minIndex, array);24 }25 if (array.length - 1 - i != maxIndex) {26 // 防止最大数在第一个，优先和最小数进行交换27 if (i == maxIndex) {28 swap(array.length - 1 - i, minIndex, array);29 } else {30 swap(array.length - 1 - i, maxIndex, array);31 }32 }33 }34 }
代码地址：
https://github.com/Gerrard-Feng/Algorithm/blob/master/Algorithm/src/com/gerrard/sort/SelectionSort.java
PS：如果存在描述或者代码错误的情况，欢迎指正，谢谢！
发表评论
最新留言
关于作者
