选择排序

作者: mapleLeaf_X | 来源:发表于2020-03-12 15:24 被阅读0次

    概念

    选择排序(selection sort) 是一种简单直观的排序算法。


    选择排序动图(copy).jpg

    原理

    第一次从待排序的数据元素中选出最小(或最大)的那个元素,存放到序列的起始位置,然后再在剩余的未排序的元素中选出最小(或最大)的元素,放到已经排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为0。

    步骤:

    1. 初始状态:无序区域为[1....n],有序区域为空;
    2. 第i(i=1,2,3...n)趟排序开始时,当前有序区域和无序区域为[1...i-1]和[i...n]。这趟排序从无需区域中选出最小的的记录min,将它和无序区域的第一个值交换,使得有序区域+1,无序区域-1.
    3. n-1趟结束后,数组就变成有序的了。


      选择排序流程图.jpg

    时间复杂度: 如果是正序的,时间复杂度是O(n),若不是,则为O(n²)

    算法稳定性:序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法

    因为交换所需要的cpu比比较所需的cpu时间多,所以选择排序(最多n-1)比冒泡排序快

    算法实现

    function selectionSort(arr) {
        // 判断是否是数组,不是则抛出错误
        if(!Array.isArray(arr)) {
            throw new Error('传入的不是数组')
        }
    
        const len = arr.length;
    
        // 判断长度是否小于等于1,是则直接返回
        if(len <= 1) {
            return arr;
        }
    
        /*
            定义一个最小值的索引minIndex,如果后边有值比当前值小,则将索引赋值给minIndex, 
        */
        for (let i = 0; i < len-1; i++) {
            let minIndex = i;
            for (let j = i + 1; j < len; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
    
            // 不相等的时候才进行交换
            if(i !== minIndex) {
                [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
            }
        }
    
        return arr;
    }
    

    github算法地址

    相关文章

      网友评论

        本文标题:选择排序

        本文链接:https://www.haomeiwen.com/subject/pvnujhtx.html