排序算法---选择排序

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跑到了后面