Partition 快排核心函数

快速排序介绍

快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

傻瓜版

下面这个代码是我之前看过，觉得是很容易理解的版本：

void quick_sort(int arr[], int left, int right)
{
    if (left < right){
    int i = left, j = right, target = arr[left];    //以第一个位置作为划分依据
    while (i < j){
        while (i < j && arr[j] > target)            //从右开始找到第一个比target小的
            j--;
        if (i < j)
            arr[i++] = arr[j];                      //把右边的一个数放到左边
        while (i < j && arr[i] < target)            //从左开始找到一个比target大的数
            i++;
        if (i < j)
            arr[j] = arr[i];                        //把左边的一个数放到刚才右边数的位置
    }
    arr[i] = target;                //把target放到中间位置
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
    }
}

搬运版

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <assert.h>
using namespace std;

//[lo, hi) : 构造轴点，轴点前的所有元素都不大于轴点值，反之都不小于轴点值
int partition(vector<int>&nums, int lo, int hi){ 
    assert(hi - lo >= 2); //partition给定的区间必须至少包含两个元素

    int p = lo + rand() % (hi - lo);
    swap(nums[lo], nums[p]);      //首先把轴点放到lo位置
    int mi = lo;
    for(int i = lo + 1; i < hi; ++i){    //遍历，这里维护一个指针mi，使得mi所指及左侧均为小于轴点值
        if(nums[i] < nums[lo])
            swap(nums[++mi], nums[i]);
    }
    swap(nums[lo], nums[mi]);        //将轴点值放到mi现在的位置，即分界点
    return mi; 
}

void quicksort(vector<int>&nums, int lo, int hi){
    //将nums[lo, hi)内的所有元素进行排序
    if(hi - lo < 2) return;

    int mi = partition(nums, lo, hi);
    quicksort(nums, lo, mi);
    quicksort(nums, mi + 1, hi);
    return;
}



int main(){
    srand(time(NULL));
    vector<int> tst;
    for(int i = 0; i < 1000; i++){
        tst.push_back(rand() % 1000);
    }


    for(auto x : tst) cout << x << " ";
    cout << endl;

    quicksort(tst, 0, tst.size());

    for(auto x : tst) cout << x << " ";
    cout << endl;

    return 0;
}