1. 復雜度與穩(wěn)定性

算法時間復雜度

最壞情況：O(n^2)

最好情況：O(nlogn)

平均情況：O(nlogn)

穩(wěn)定性：不穩(wěn)定排序

2. 過程介紹

快速排序是考察次數(shù)最多的排序，無論是在大學專業(yè)課的期末考試，還是在公司的面試測試題目中，快速排序都極大的被使用，在實際中快速排序也極大的被使用，如STL中的sort底層就是一個快速排序。

首先在數(shù)組中選擇一個基準點，然后分別從數(shù)組的兩端掃描數(shù)組，設兩個指示標志（low指向起始位置，high指向末尾)，首先從后半部分開始，如果發(fā)現(xiàn)有元素比該基準點的值小，就交換low和high位置的值，然后從前半部分開始掃描，發(fā)現(xiàn)有元素大于基準點的值，就交換low和high位置的值，如此往復循環(huán)，直到low>=high,然后把基準點的值放到high這個位置。一次排序就完成了。

以后采用遞歸的方式分別對前半部分和后半部分排序，當前半部分和后半部分均有序時該數(shù)組就自然有序了。

3.圖示過程

可以看出，在第四躺時已經達到順序，但是任還是會繼續(xù)計算幾趟直到完成全部運算

4. 相關的代碼

#include<iostream>
using namespace std;
 
void qucik_sort(int a[],int low,int high) {
    int i,j,temp;
    i=low;
    j=high;
    if(low<high) {
        temp=a[low];    //設置樞軸
        while(i!=j) {
            while(j>i&&a[j]>=temp) {
                --j;
            }
            if(i<j) {
                a[i]=a[j];
                ++i;
            }
 
            while(i<j&&a[i]<temp) {
                ++i;
            }
            if(i<j) {
                a[j]=a[i];
                --j;
            }
        }
        a[i]=temp;
        qucik_sort(a,low,i-1);
        qucik_sort(a,i+1,high);
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    qucik_sort(a,0,n-1);
    for(int i=0; i<n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}