每天一点算法-简单选择排序 (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)。

感谢阅读！欢迎关注！持续升级中…