每天一点算法-简单选择排序 (Day7)

介绍

今天给大家介绍选择排序算法中的——简单选择排序，该排序算法很容易理解，一句话表述:

每一次遍历找到最小的数和最前面的待排序数互换位置，直到所有数都已排序。

还是以这组被我用各种算法玩的待排序数为例（升序, 粗体字为已排序数；标红字为需互换数）：[77, 6, 37, 96, 34, 6, 14]

例子

js实现如下(升序)：

function sort(arr) {
　　for(let i = 0; i < arr.length; i++){
　　    let minIndex = i;
　　    for(let j = i + 1; j < arr.length; j++){
　　        if(arr[j] < arr[minIndex]){
　　            minIndex = j;
　　        }
　　    }
　　    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; //解构互换位置
　　}
　　return arr;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]

时间复杂度

遍历次数的计算与冒泡排序类似：n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，所以时间复杂度为O(n^2)。

感谢阅读！欢迎关注！持续更新中...