Heading

选择排序的思想是：每一趟（如第 i 趟）在后面 n-i+1(i=1,2,...,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第 i 个元素，直到 n-1 趟选完，待排序序列只剩下一个元素。

点击查看代码

/**
 * 选择排序
 * @param {*} arr 
 * @param {*} n 
 */
export function SelectionSort(arr = [], n = 0) {
    let i, j, min;
    for (i = 0; i < n; i++) {
        min = i
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        if (min !== i) Swap(arr, i, min);
    }
    return arr
}

性能分析如下：

• 空间效率：仅使用常数个辅助单元，空间复杂度为O(1)。
• 时间效率：元素的移动次数很少，不会超过3(n-1)次，最好的情况是移动 0 次，此时对应的表已经有序；但元素间的比较次数与序列初始状态无关，始终是n(n-1)/2次，因此时间复杂度为O(n^2)。
• 稳定性：在第 i 趟找到最小元素后，和第 i 个元素交换，可能会导致第 i 个元素与其含有相同关键字元素的相对位置发生变化。