快速排序

• Time Best: O(N*logN)
• Time Average: O(N*logN)
• Time Worst: O(N^2) 数组本身趋近于有序（不论逆序/正序）或者所有元素都相等（特殊的有序）
• Space Worst: O(logN) 递归栈占用的空间

function quickSort(arr, l, r) {
    if(l >= r) return
    let x = arr[l + r >> 1] // 选一个标
    let i = l - 1, j = r + 1 // 注意这里的初始值
    while(i < j) {
        // 将数组分为<x和>x两段，<=x的在左边，>=x的在右边
        do{ i++ } while(arr[i] < x)
        do{ j-- } while(arr[j] > x)
        // 直到遇到不符合的i, j，将他俩交换
        if(i < j) {
            swap(arr, i, j)
        }
    }
    // 递归左半边
    quickSort(arr, l, j) // 注意这里是以j为分割点
    // 递归右半边
    quickSort(arr, j + 1, r)
}

总体思路：
1. 选择分界点x (l, r, l+r/2)
2. 左边所有数 left <= x, 右边所有数 right >= x
3. 递归排序left，递归排序right

求第K小的数

同样的思路，可以使用快速选择算法。
1. 假设当前的left区间长度 SL <= k，则说明第k小的数在右半边，递归right部分，找第k-SL个数
2. 假设当前的left区间长度 SL > k，则说明第k小的数再左半边，递归left部分，找第k个数

时间复杂度：由于每次只递归一半，则 N + N/2 + N/4 + … = N * (1 + 1/2 + 1/4 …) 即 <= 2 * N。所以复杂度是 O(N)。

归并排序

• Time Best: O(N*logN)
• Time Average: O(N*logN)
• Time Worst: O(N*logN)
• Space Worst: O(N) 临时数组

function mergeSort(arr, l, r) {
    if (l >= r) return;
    const mid = (l + r) >> 1;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    let i = l, // 左半段起点
        j = mid + 1, // 右半段起点
        temp = [], // 归并放入的临时数组
        k = 0; // 临时数组的idx指针
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= r) {
        temp[k++] = arr[j++];
    }
    // 起点是l，终点是r
    for (let i = l, j = 0; i <= r; i++, j++) {
        arr[i] = temp[j]; // 拷贝到arr里去
    }
}

堆排序

• Time Best: O(N*logN)
• Time Average: O(N*logN)
• Time Worst: O(N*logN)
• Space Worst: O(1)

冒泡排序

双重循环，外层循环每次冒泡结束的end位置，内层循环开始枚举每一对儿的起始，每次比较pair[HTML_REMOVED]的大小，直到i。

• Time Best: O(N) 当数组已经有序时最快
• Time Average: O(N^2)
• Time Worst: O(N^2) 当数组是逆序时最慢
• Space Worst: O(1)

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {  // 相邻元素两两对比
                swap(j, j + 1)
            }
        }
    }
    return arr;
}

插入排序

双重循环，最外层循环枚举每个数arr[i]，内层循环是枚举arr[i]可以插入的位置j，从i开始往前找。

• Time Best: O(N) 当数组
• Time Average: O(N^2)
• Time Worst: O(N^2)
• Space Worst: O(1)

function insertionSort(arr) {
    const n = arr.length
    for (let i = 1; i < n; i++) {
        // 寻找元素 arr[i] 合适的插入位置
       for(let j = i; j > 0; j --) {
           if(arr[j] < arr[j - 1])
                swap(j, j - 1)
            else
                break
       }
    }
    return arr
}

选择排序

双重循环，外层循环是枚举选择的起点i，内层循环是找到i之后的最小值，记为minIndex，然后交换i和minIndex。

• Time Best: O(N^2)
• Time Average: O(N^2)
• Time Worst: O(N^2)
• Space Worst: O(1)

function selectionSort(arr) {
    const n = arr.length
    let minIndex
    for (let i = 0; i < n - 1; i++) {
        minIndex = i
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) { // 寻找最小的数
                minIndex = j // 将最小数的索引保存
            }
        }
        swap(i, minIndex)
    }
    return arr
}