算法入门 - 选择排序

选择排序的简单程度可能仅次于冒泡排序，甚至在名称的理解上要胜过冒泡。谁又能把冒泡和算法联系到一起呢？个人认为冒泡是一个失败的命名，仅次于套接字和句柄的翻译。

算法思路

先简单介绍一下选择排序的思路，甚至不用像插入排序那样列出几个步骤来。以从小到大排序为例，首先在整个列表中找到一个最小的元素与第一个元素交换，然后再从剩下未排序的列表中找到一个最小的元素放在第二位，以此类推直接整个列表排序完毕。就是在不停的比较，然后交换，下面看一个动画演示就一目了然。

复杂度与适用场景

这里需要做一个简单的计算，来算一个总的比较次数。第一次会比较n-1次，第二次就是n-2，那么总的次数就是：N = (n-1)+(n-2)+...+1 = n*(n-1)/2。这是个等差数列求和，出现了 n^2，我们忽略参数可以得出这里的复杂度是：O(n^2)。也是一个较慢的算法。除了比较次数，交换也需要大量的步骤。最好的情况是完全有序，那一次都不用交换；完全逆序的情况下，就需要交换n-1次。但比较次数是实打实的，无论什么情况都会比较这么多次。也不是完全没用，当对空间复杂度的要求比较严苛时，只做交换，没有额外产生新的临时列表就有了价值。同样的情况下，交换所需要的 cpu 时间要高于比较，所以当 n 值较小时，比冒泡排序性能好一些。

实现

其中 TestHelper 这个工具类参考这篇文章：如何开始

public static void sort(Integer[] arr, Integer size) {    for (int i = 0; i < size; i++) {        int minIndex = i;        for (int j = i + 1; j < size; j++) {            if (arr[j] < arr[minIndex])                minIndex = j;        }        TestHelper.swap(arr, minIndex, i);    }}

作者：Carleslucky

链接：https://juejin.cn/post/7026733868350701576

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。