排序算法之选择排序

文章目录

1. 1. 排序
2. 2. 选择排序
   1. 2.1. 规则
   2. 2.2. 时间复杂度
   3. 2.3. 优缺点
3. 3. 算法实现
   1. 3.1. js代码
   2. 3.2. 分析
4. 4. 参考文档

算法是每一个程序员都应该了解的知识，正所谓：不会算法的程序员人生是不完整的。排序算法是算法界的基础了，并且在各种面试中被问到最多的算法题就是排序了，所以先来理解排序算法中初级的排序——选择排序。

排序

排序，就是将一组对象按照某种逻辑顺序重新排列的过程，其目的就是将一组”无序”的记录序列调整为”有序”的记录序列。

假定，在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变（即在排序前，a[i]=a[i+1]，排序后他们的位置是不变的），则称这种排序算法是稳定的，否则为不稳定排序。

排序算法分为很多种，常见的有：快速排序、希尔排序、堆排序、选择排序、插入排序和归并排序等…

选择排序

一种极简单的排序算法。

规则

首先，找到数组中最小的那个元素；
其次，将它和数组的第一个元素交换位置；
再次，在剩下的元素中找到最小的元素，将它与第二个元素交换位置；
如此反复，直到将整个数组排序。

时间复杂度

选择排序的内循环只是在比较当前元素与已知的最小元素（以及将当前索引加1和检查是否代码越界）。交换元素的代码写在内循环之外，每次交换都排定一个元素。

交换操作介于 0 和 (n-1) 次之间，比较操作为 n(n-1)/2 次，赋值操作介于 0 和 3(n-1) 次之间。

因此，比较次数 O(n^2)，交换的总次数是 O(n) ，算法的时间效率取决于比较的次数。

优缺点

1. 运行时间和输入无关，为了找出最小的元素，它需要先整体扫描一遍数组，但这并不能为之后的迭代提供什么信息。所以如果有一组有序的数组或值全部相等的数组和一个无序数组所用的排序时间是一样长的。

2. 数据移动少，每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换（交换次数和数组的大小是线性关系）。其他任何算法都是线性对数或平方级别。

算法实现

js代码

example.js

function sort(arr) {
    var temp;
    var pos = 0;
    for (var i = 0; i < arr.length-1; i++) {
        pos = i;
        for (var j = i+1; j < arr.length; j++) {
            if (arr[j] < arr[pos]) {
                pos = j;
            };
        };
        temp = arr[i];
        arr[i] = arr[pos];
        arr[pos] = temp;
    };
};

分析

为了体现选择排序的实现过程，输出最终的由小到大的排序数组，我在上面的代码中加入了一些打印语句，方便我可以直观的看到sort()函数是如何遍历并且交换元素的。

可以看出，我打印出了每次参数的变化情况，接下来我们来看看在sort()函数内究竟发生了什么：

第一次循环会遍历整个数组，此时 i = 0，逐个比较元素后找到最小值，并把最小元素下标赋值给 pos，在执行到 st.6 时数组第 i 位置的元素和第 pos 位置的元素互相交换位置，也就是把最小值移到了数组第一位。

第二次循环 i = 1，此时遍历会排除数组第 i 位置左边的元素，也就是排除了第一位置的元素再开始遍历。比较其余数字后，同样把最小元素下标赋值给 pos，最后把数组第 i 位置元素和第 pos 位置元素互换位置，也就是把最小值移到了第二位。
此时，因为数组中本身第二位置元素就是当前最小值了，所以在打印中看不出元素交换的痕迹，但是代码确实是执行了一次交换赋值，只不过是把第二位又移到了第二位。

第三次循环和第四次循环跟上面步骤一样。最后输出排列好的数组。

从上图就可以看出，选择排序的排序轨迹成对角线状，而无论下一元素是否已经按大小排列好，它都要遍历剩余元素做比对后交换位置。所以，如果你有一组已经排列好的数组，或排列变动并不大的数组，使用选择排序是很不划算的。

并且，选择排序是一种不稳定排序，它会打乱你数组中相同元素的位置。比如：[9,5,9,3,1]排序这个数组会先把第一元素’9’与最后一个元素’1’交换，这时本应在第三个元素的’9’就会排在它前面。当然，在视觉上是无所谓的，但是稳定排序就不会出现这样的问题。

参考文档

• 图灵程序设计丛书–算法(第4版)
• 选择排序·源代码

---