普通快速排序

全称 Quicksort
特点
- 不稳定
- 时间复杂度
  - 最坏 O(n2)，只要提前打乱就不容易出现最坏的情况
  - 最优和平均 O(nlogN)
原理
- 指定一个位置pivot(一般是最左的头部)
  - 可以先打乱数组，保证不出现最坏情况退化至n2
- 进入循环
  - 从右向左找到第一个位置r，其值比p处值小
    - 这里用>号判断推进r--
    - 这里注意: 升序排序的话，一定要先从右边找r，再去找l，反之亦然
      - 为什么？因为要让r抢先占领比pivot大的值然后抢先比较成功推进r--达成l==r，从而保证l指向的值在退出循环时(即l == r时)永远小于等于pivot处值，就算换到pivot处也没关系
      - 反过来想，如果让l抢先占领比pivot处小的值却误比较推进l++达成l==r，这种误推进下可能会出现“相遇处值比pivot处更大”却换到pivot处
  - 从左向右找到第一个位置l，其值比p处值大
    - 这里用<=号判断推进l++
    - 这里注意: 一定要加等号，否则这条语句就废了
      - 为什么？因为l处值初始就等于pivot处值，那就永远不会从pivot处离开
      - 但奇怪的是，不加等号废了的情况下也能勉强正确排序
  - 如果l仍然小于r，那交换这两个值
  - 进入下一个循环，继续往中间找到这样的两个位置，不断进行交换
- 循环结束后，除了pivot处之外，数据就会分成左右两段，左边段的值均比pivot处值小，右边段的值均比pivot处值大，分界点就是l和r最终的位置
  - 这里l和r最终位置在我们先减l再加r的判断顺序下，是小于等于pivot处值的，所以可以交换分界点处的值和pivot处值
- 然后把这两段分别进行递归，一段终止于l - 1，一段开始于l + 1再次调用上面的算法
  - 递归结束的条件就是这一段的长度为1或0

let quickSort = (arr, si, ei) => {
    if (si >= ei) return;
    let pivot = si, l = si, r = ei;
    while (l !== r) {
        while(l < r && arr[r] > arr[pivot]) r--;
        while(l < r && arr[l] <= arr[pivot]) l++;
        if (l < r) [arr[l], arr[r]] = [arr[r], arr[l]];
    }
    [arr[pivot], arr[r]] = [arr[r], arr[pivot]];
    quickSort(arr, si, l - 1);
    quickSort(arr, l + 1, ei);
}

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);
    quickSort(testArr, 0, testArr.length - 1);
    console.log(testArr);
})()

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

void quickSort(vector<int>& nums, int si, int ei) {
    if(si >= ei) return;
    int pivot = si, l = si, r = ei;
    while(l != r){
        while(l < r && nums[r] > nums[pivot]) r--;
        while(l < r && nums[l] <= nums[pivot]) l++;
        if(l < r) swap(nums[l], nums[r]);
    }
    swap(nums[r], nums[pivot]);
    quickSort(nums, si, l - 1);
    quickSort(nums, l + 1, ei);
};

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);
    quickSort(testArr, 0 , testArr.size() - 1);
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}

Keyboard shortcuts

普通快速排序