快速排序算法实现

#include <iostream>
#include<vector>
using namespace std;


void quickSort(vector<int>&a,int first , int last){
    if(first >= last){
        return;
    }
    int i = first,j = last;
    int key = a[first];//选择当前数字中第一个数作为基准key
    while(i < j){
        while(i < j && a[j] > key){
            j--;
        }
        a[i] = a[j];//在数组的后面遇到了比基准key小的数,放到前面去
        while(i < j && a[i] < key){
            i++;
        }
        a[j] = a[i];//在数组的前面遇到了比基准key大的数,放到后面去,刚好覆盖上次那个比基准大的数的位置
    }
    a[j] = key;//此时i==j,这个位置应该就是我们的基准key应该放到的地方
    quickSort(a,first,j-1);//递归对目前的key左边部分使用快速排序
    quickSort(a,i+1,last );//递归对目前的key右边部分使用快速排序
}

int main()
{
    vector<int>a = {22,32,54,79,154,2,10,0,-6,48,99};
    quickSort(a,0,10);
    for(int i = 0;i<11;i++){
        cout<<a[i]<<" ";
    }
}

快速排序是综合性能最好的排序方式,平均时间复杂度为O(nlogn),且不具有稳定性。

当序列已经是递增序列的时候,快速排序此时的时间复杂度最高,为O(n²)。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注