选择排序

2024年04月03日

柏拉文

越努力，越幸运

一、认识

---

选择排序简单直观，英文称为Select Sort，先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。

特点:

• 不稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排。选择排序的过程会破坏原有数组中相同关键字的相对次序，所以选择排序是不稳定算法
• 原地排序: 在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序
• 排序方式: In-place (不占用额外内存，只占用常数内存)
• 时间复杂度: O($n^{2}$) [n 代表数据规模及数据量大小]
• 空间复杂度: O(1)

扩展:

• 排序算法的稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

• 冒泡排序和选择排序的相同点和不同点:
  • 相同点:
    • 都是两层循环，时间复杂度都为 O(n^2)
    • 都只使用有限个变量，空间复杂度 O(1)。
  • 不同点:
    • 冒泡排序在比较过程中就不断交换；而选择排序增加了一个变量保存最小值 / 最大值的下标，遍历完成后才交换，减少了交换次数。
    • 冒泡排序法是稳定的，选择排序法是不稳定的。

二、思想

---

先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。

三、实现

---

3.1 一元选择排序

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

性能分析:

• 时间复杂度:O(n^2)
• 空间复杂度:O(1)

3.2 二元选择排序

思路:

• 在二元选择排序的外层 for 循环中 i 只需要加到 arr.length / 2
• 在二元选择排序的内层 for 循环中 j 只需要加到 arr.length - i
• 当 minIndex == maxIndex 时，说明后续所有的元素都相等，此时已经排序完成，可以提前跳出循环。

function sortArray(nums) {
    let minIndex;
    let maxIndex;
    for(let i=0;i<Math.floor(nums.length/2);i++){
        minIndex=i;
        maxIndex=i;
        for(let j=minIndex+1;j<nums.length-i;j++){
            if(nums[minIndex]>nums[j]){
                minIndex=j;
            }
            if(nums[maxIndex]<nums[j]){
                maxIndex=j;
            }
        }
        if(minIndex==maxIndex) break;
        [nums[i],nums[minIndex]]=[nums[minIndex],nums[i]];
        if(maxIndex==i){
            maxIndex=minIndex;
        }
        [nums[nums.length-1-i],nums[maxIndex]]=[nums[maxIndex],nums[nums.length-1-i]];
    }
    return nums
};

性能分析:

• 时间复杂度:O(n^2) 二元选择排序虽然比选择排序要快，但治标不治本，二元选择排序中做的优化无法改变其时间复杂度
• 空间复杂度:O(1)