快速排序

基础知识

名称 : 快速排序

性质 : 不稳定的排序算法

用途 : 分治思路的排序

复杂度 : 时间 O(nlogn) 空间 O(1)

代码实现

/************************************************************************
    > File Name: quick_sort2.cpp
    > Author: Lao Zhenyu
    > Mail: LaoZhenyu_961112@163.com
    > Created Time: 五  1/15 17:48:29 2021
************************************************************************/

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;

void quickSort(vector<int> &arr, int left, int right){
    if(left >= right)   return;
    int i,j,base;
    base = arr[left];
    i = left, j = right;
    while(i < j){
        while(arr[j] >= base && i < j)
            j--;
        while(arr[i] <= base && i < j)
            i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    arr[left] = arr[i];
    arr[i] = base;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}



int main(){
    vector<int> arr{1,3,2,6,5,4,9,7,8,};
    quickSort(arr, 0, arr.size() - 1);
    for(int n : arr){
        cout << n << endl;
    }
    return 0;
}