三路快速排序

• 全称 3-way Radix Quicksort

• 原理

  • 是快速排序和基数排序的混合
  • 在随机选取分界点m后，把数组分为三个部分
    • 小于m，(分界j)，等于m，(分界k)，大于m
  • 避免了分界点处存在大量相同数据使得数据规模无法迅速缩小的问题

let threeWayQuickSort = (arr, si, ei) => {
    if (si >= ei) return;
    const len = ei - si + 1;
    const random = (Math.random() * arr.length) >>> 0;
    const pivot = arr[si + random % len];
    let i = si, j = si, k = ei + 1;
    while (i < k) {
        if (arr[i] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
            j++;
        } else if (arr[i] > pivot) {
            --k;
            [arr[i], arr[k]] = [arr[k], arr[i]];
        } else i++;
    }
    threeWayQuickSort(arr, si, j);
    threeWayQuickSort(arr, k, 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);
    threeWayQuickSort(testArr, 0, testArr.length - 1);
    console.log(testArr);
})()

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

void threeWayQuickSort(vector<int>& arr, int si, int ei){
    if (si >= ei) return;
    int len = ei - si + 1;
    const int pivot = arr[si + rand() % len];
    int i = si, j = si, k = ei + 1;
    while (i < k) {
        if (arr[i] < pivot) swap(arr[i++], arr[j++]);
        else if (arr[i] > pivot) swap(arr[i], arr[--k]);
        else i++;
    }
    threeWayQuickSort(arr, si, j);
    threeWayQuickSort(arr, k, 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);
    threeWayQuickSort(testArr, 0, testArr.size() - 1);
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}