排序算法---选择排序

2023-12-14 05:41:10

1.实现流程:?

1. 把第一个没有排序过的元素设置为最小值;

2.?遍历每个没有排序过的元素;

3.?如果元素 < 现在的最小值;

4.?将此元素设置成为新的最小值;

5.?将最小值和第一个没有排序过的位置交换

选择排序执行流程

2.代码实现

        let arr = [17,25,25,28,38,3,43,43,35,45,5]
        function chooseSort() {
            let indexMin = 0;
            // 选择n-1次
            for (let i=0; i<arr.length-1; i++) {
                let indexMin = i;
                for (let j=i+1; j<arr.length; j++) {
                    if (arr[j]<arr[indexMin]) {
                        indexMin = j;
                    }
                }
                if (indexMin != i) {
                    let temp = arr[i];
                    arr[i] = arr[indexMin];
                    arr[indexMin] = temp;
                }
            }
            console.log(arr)
        }
        chooseSort()

运行结果:

3.复杂度分析

1. 时间复杂度:找出执行次数最多的语句即可

if (arr[j]<arr[indexMin]) {
      indexMin = j;
}

基于上述每一趟比较的次数,可以得到总的比较次数,就是这个判断语句执行的次数

=> 当i=0时, 需要比较n-1-0次

? ? ?当i=1时,需要比较n-1-1次

? ? ?......

? ? ?当i=n-3时, 需要比较n-1-(n-3) = 2

? ? ?当i=n-2时, 需要比较n-1-(n-2) = 1

? ? ?当i=n-1时, 需要比较n-1-(n-1) = 0

=> ?(n-1)+(n-2)+(n-3)+...+1+0 = [n(n-1)]/2 ?= n^2/2 - n/2 + 1/2

=> 去掉系数、低阶和常量 ?

=> 则时间复杂度为 ?O(n^2)

2. 空间复杂度: 选择排序中并没有用到额外的空间,所以空间复杂度为 O(1)

3. 选择排序是不稳定的排序算法:从上述的视频可以看出,数组中有两个43,然而在排完序后,原本前面的43跑到了后面

文章来源:https://blog.csdn.net/m0_61495539/article/details/134911070
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。