选择排序

• 全称 Selection sort

• 特点

  • 位于i的数会被换到后面去，不稳定
  • 时间复杂度
    • 最优、平均、最坏均为O(n2)

• 原理

  • 外层: 0 ~ n-1 循环
  • 内层: 找到后面 (i+1 ~ n-1) 区间的最小数下标
    • 通过不断比较替换来找
    • 等内层循环结束后再统一换到i位置

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

let shuffle = (arr) => {
    let n = arr.length;
    while (n > 0) {
        const random = (Math.random() * n--) >>> 0;
        [arr[random], arr[n]] = [arr[n], arr[random]];
    }
    return arr;
}

(() => {
    let testArr = [5, 7, 3, 4, 2, 6, 1];
    shuffle(testArr);
    selectionSort(testArr);
    console.log(testArr);
})()

#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;

void selectionSort(vector<int>& arr) {
    int len = arr.size();
    for(int i = 0; i < len; ++i){
        int ith = i;
        for(int j = i + 1; j < len; ++j){
            if(arr[j] < arr[ith]) ith = j;
        }
        swap(arr[i], arr[ith]);
    }
};

void shuffle(vector<int>& arr) {
    int n = arr.size();
    srand(time(NULL));
    while (n--) {
        const int random = rand() % arr.size();
        swap(arr[n], arr[random]);
    }
}

int main() {
    vector<int> testArr = {5, 7, 3, 4, 2, 6, 1};
    shuffle(testArr);
    selectionSort(testArr);
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}