基础算法：选择排序

[cj0x39e]

问题

给定下面的数组，请使用 选择排序 算法使其按从小到大的顺序排列？

const list = [1, 7, 9, 8, 3, 2, 10];

...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔 ...🤔

丰橙解答

/**
 * 查找列表最小值索引
 * @param {Array} list 待查找的列表
 */
function findSmallest (list) {
    let smallest = list[0];
    let smallestIndex = 0;

    // 遍历查找，根据判断情况不断更新最小值及其索引
    for (let i = 0; i < list.length; i++) {
        if (list[i] < smallest) {
            smallest = list[i];
            smallestIndex = i;
        }
    }

    // 最后返回当前查找列表的最小值的索引
    return smallestIndex;
}

/**
 * 选择排序算法（升序）
 * @param {Array} list 待排序的列表
 */
function selectionSort (list) {
    let newList = [];

    // 每次遍历找出其中的最小值的索引从待排序列表中删除，并塞到新的列表
    // 遍历完成新的列表便是从小到大排序好的列表
    for (let i = list.length - 1; i >= 0; i--) {
        const smallestIndex = findSmallest(list);
        newList.push(list.splice(smallestIndex, 1)[0])
    }

    return newList;
}

// test
const list = [1, 7, 9, 8, 3, 2, 10];
console.log(selectionSort(list));  // [ 1, 2, 3, 7, 8, 9, 10 ]

const listTwo = [2, 3, 1, 1, 1, 1, 1];
console.log(selectionSort(listTwo));  // [ 1, 1, 1, 1, 1, 2, 3 ]

时间复杂度

O(n x n)

可视化链接

https://algorithm-visualizer.org/brute-force/selection-sort

测试链接

因为 leetcode 测试用例很多，所以在 leetcode 测试通过就行了: https://leetcode-cn.com/problems/sort-an-array/

[surprisingwu]

sort函数是选择排序算法么?

[cj0x39e]

sort函数是选择排序算法么?

最新的 V8 ，使用的是 TimSort

[guxinduyin666]

/**

• 选择排序
• 查找列表最小值索引
• @param {Array} list 待查找的列表 */ function selectionSort(list) { for(let i=0,len=list.length;i<len;i++){ for(let j=i+1;j<len;j++){ if(list[i]>list[j]){ [list[i],list[j]]=[list[j],list[i]];//交换位置 } } } }

[cj0x39e]

/**

• 选择排序
• 查找列表最小值索引
• @param {Array} list 待查找的列表 */ function selectionSort(list) { for(let i=0,len=list.length;i<len;i++){ for(let j=i+1;j<len;j++){ if(list[i]>list[j]){ [list[i],list[j]]=[list[j],list[i]];//交换位置 } } } }

这个更符号冒泡排序的特征O(∩_∩)O哈！

[guxinduyin666]

/**

• 选择排序
• 查找列表最小值索引
• @param {Array} list 待查找的列表 */ function selectionSort(list) { for(let i=0,len=list.length;i<len;i++){ for(let j=i+1;j<len;j++){ if(list[i]>list[j]){ [list[i],list[j]]=[list[j],list[i]];//交换位置 } } } }

这个更符号冒泡排序的特征O(∩_∩)O哈！

好像是的，我再写一个

[guxinduyin666]

       function selectionSort(list){
            let len=list.length;
            if(len==0){return }
            for(let i=0;i<len;i++){
                let minIndex=i;
                for(let j=i+1;j<len;j++){
                    if(list[minIndex]>list[j]){
                        minIndex=j
                    }
                }
                [list[i],list[minIndex]]=[list[minIndex],list[i]];
            }
        }

[guxinduyin666]

这个应该是选择排序的算法

[liubailing]

就在你实现的代码里面 选择排序 不稳定性体现在哪里。或者说哪里可能会造成不稳定