手写选择排序算法

问题

手写实现选择排序算法。

解答

选择排序是一种简单直观的排序算法。工作原理是：在未排序序列中找到最小元素，放到已排序序列的末尾，重复此过程直到所有元素排序完成。

算法步骤

1. 在未排序序列中找到最小元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾
3. 重复步骤 2，直到所有元素排序完毕

代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        // 在未排序部分找最小值
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换位置
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    
    return arr;
}

时间复杂度

• 最佳情况：O(n²)
• 最差情况：O(n²)
• 平均情况：O(n²)

关键点

• 每次从未排序部分选出最小元素，放到已排序部分的末尾
• 需要两层循环：外层控制已排序部分的边界，内层查找最小值
• 时间复杂度始终为 O(n²)，不受数据初始状态影响
• 是不稳定排序算法，相同元素的相对位置可能改变