Day17:[排序演算法]Selection Sort - 选择排序法

从今天开始要来理解排序演算法了!简单来说就是经过一连串的步骤将数字由小排到大或是由大排到小的演算法，下图列出几种常见的排序演算法，像是插入排序法、气泡排序法、合并排序法等等。

图片来源:https://dev.to/edwardcashmere/sorting-algorithms-2541

今天要介绍的是选择排序法，先找出数字里面最小的或最大的数，第一个步骤是先找最小的数字，再跟尚未排序的数字的最左边的互换。

假设现在有个尚未排序的阵列:[ 29, 10, 14, 37, 13]

• 尚未排序的数字: 29, 10, 14, 37, 13
• 排序好的数字:无

选择排序法的执行步骤:

1. 发现尚未排序的数字中10为最小值，与尚未排序中最左边的数字29交换，此时阵列为[10, 29, 14, 37, 13]
   

• 尚未排序的数字: 29, 14, 37, 13
• 排序好的数字:10

2. 发现尚未排序的数字中13为最小值，与尚未排序中最左边的数字29交换，此时阵列为[10, 13, 14, 37, 29]
   

• 尚未排序的数字有 14, 37, 29
• 排序好的数字:10, 13

以此类推，直到所有数字都由小排到大

图档来源:https://visualgo.net/zh/

用js实作选择排序法

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

selectionSort([29, 10, 14, 37, 13]);

时间复杂度

• 在最差的情况下， 时间复杂度是O(n²)
• 在最佳的情况下 ， 时间复杂度是O(n²)
• 在平均情况下，时间复杂度为 O(n²)

参考资料:Sorting Algorithms