面试时，算法经常会遇到，特别是一些常见的算法。 张工毕业3年了，一直在一家创业公司做java开发，最近到某知名互联网公司面试，做了笔试题后，面试官看了觉得还不错，于是想进一步考察张工的编码能力，就让他手写选择排序算法，张工写不出来，面试官说：你都毕业3年了，连个选择排序法都写不出来，我参加计算机等级考试就会这个了。张工一脸的无助，不过确实不应该，类似选择排序这样基础的算法，平时应该要掌握好才对。 小编之前参加的笔试也遇到了手写排序算法的情况，关于选择排序可能基本都能写出来，但要是能把程序再优化一下，那就更好了，相信能给面试官留下更好的印象。 我们先来看什么选择排序法：
选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 稳定性 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。 举个例子，序列6 8 6 3 9，我们知道第一遍选择第1个元素6会和3交换，那么原序列中两个6的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。 关于时间复杂度 选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。其中直接选择排序的时间复杂度为O（n*n），空间复杂度为O（1）。树形选择排序的时间复杂度为O（nlog2n），空间复杂度为O（n）。堆排序的平均时间复杂度为O（nlog2n），效率高，但是实现相对复杂，空间代价为O（1）。
我们来看用java编写的选择排序算法代码
/** * 选择排序 * * @param arr */ public static void selectionSort(int[] arr) { int min; int length = arr.length; for (int i = 0; i < length; i++) { // 初始化未排序序列中最小数据数组下标 min = i; for (int j = i + 1; j < length; j++) { // 在未排序元素中继续寻找最小元素，并保存其下标 if (arr[j] < arr[min]) { min = j; } } // 将未排序列中最小元素放到已排序列末尾 if (min != i) { swap(min, i, arr); } } }
/** * 交换顺序 * * @param x * @param y * @param arr */ private static void swap(int x, int y, int[] arr) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; }
调用实例 public static void main(String[] args) { int arr[] = {2, 17, 2, 11, 7, 6, 19, 9, 14, 20, 17, 13, 14, 2, 10}; System.out.println(String.format("original array = %s\n", Arrays.toString(arr))); selectionSort(arr); System.out.println(String.format("sorted array = %s\n", Arrays.toString(arr))); } 输出结果
对于选择排序算法，要是还是不太好理解，我们来看一下动画图，这样会更容易理解些。
不知你对选择排序算法是否完全理解。
选择排序法基本来说还是挺不错的，数据规模不大时，还是推荐使用的，但相对于其他的排序算法（譬如快速排序）效率还是明显有些不足。 小编认为，关于选择排序法思想还是挺重要，要重视。
-END-
万水千山总是情，点个 “在看” 行不行
