数据结构 - 快速排序

一趟快速排序（partition）

• 1. 设置 pivot = nums[left]
     image.png
• 2. right指针从右向左移动，如果left < right && nums[right] >= pivot， 则 right--，循环执行，直到不满足条件。将 nums[right] 赋值给 nums[left] ：nums[left] = nums[right]
     image.png
• 3. left指针从左向右移动，如果left < right && nums[left] <= pivot，则 left++，循环执行，直到不满足条件。将 nums[left] 赋值给 nums[right]：nums[right] = nums[left]
     image.png
• 4. 如果 left < right，循环执行步骤2,3；
• 5. 将 pivot 赋值给 nums[left]：nums[left] = pivot，返回left (pivot_idx);

时间复杂度

• O(nlogn)

代码实现

• printVector需自己实现；

#include <iostream>
#include <vector>
#include "print.h"

using namespace std;

template <typename T>
int partition(vector<T>& nums, int left, int right){
    // 一趟快速排序
    T pivot = nums[left];
  
    // nums[left], nums[right] 和 pivot 进行大小对比
    while(left < right){
        while(left < right && nums[right] >= pivot)
            right --;
        nums[left] = nums[right];

        while(left < right && nums[left] <= pivot)
            left ++;
        nums[right] = nums[left];
    }

    // pivot赋值
    nums[left] = pivot;
    return left;
}
/**
 * 快速排序
 * @tparam T
 * @param nums
 * @param left
 * @param right
 */
template <typename T>
void quickSort(vector<T>& nums, int left, int right){
    // 此处是 if 判断
    if(left < right){
        int pivot_idx = partition(nums, left, right);
        quickSort(nums, left, pivot_idx-1);
        quickSort(nums, pivot_idx+1, right);
    }
}

// 打印数组
template <typename T>
void printVector(vector<T> nums){
    for(int i=0; i<nums.size(); i++){
        cout<<nums[i]<<" ";
    }
    cout<<endl;
}

int main(){

    vector<int> nums={1,4,5,3,2};

    printVector(nums);
    quickSort(nums, 0, 4);
    printVector(nums);

    return 0;
}

参考资料

• 快速排序的Python实现：https://www.jianshu.com/p/2b2f1f79984e