快速排序是冒泡排序的一種改進(jìn)。（冒泡排序是比較相鄰的數(shù)，并使小的在前大的在后）
核心思想為：每一趟排序都選取一個(gè)基準(zhǔn)數(shù)，將數(shù)據(jù)通過基準(zhǔn)數(shù)分割成獨(dú)立的兩部分，左邊部分的數(shù)小于右邊部分的數(shù)，且在一趟排序完成后使基準(zhǔn)數(shù)在正確的位置上。

目前有兩種選擇基準(zhǔn)數(shù)的方法。
1.標(biāo)準(zhǔn)快排：選取數(shù)組第一個(gè)數(shù)為基準(zhǔn)數(shù)。（這種方法的缺點(diǎn)在于對(duì)于基本有序的序列排序反而很慢）
2.改進(jìn)快排：選取數(shù)組中間的數(shù)為基準(zhǔn)數(shù)，比普通快排要快一些。

方法一代碼如下

#include <bits/stdc++.h>
using namespace std;
int a[100005],n;

void qsort(int low, int high)
{
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    //開頭的數(shù)為基準(zhǔn)數(shù)
    int key = a[low];
    while (true)
    {
        /*從左向右找比key大的值*/
        while (a[++i] < key)
        {
            if (i == high){
                break;
            }
        }
        /*從右向左找比key小的值*/
        while (a[--j] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交換i,j對(duì)應(yīng)的值*/
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //基準(zhǔn)數(shù)與j對(duì)應(yīng)值交換,因?yàn)榕c基準(zhǔn)數(shù)交換位置后在其前面，所以交換的數(shù)要比基準(zhǔn)數(shù)小，所以選j
    int temp = a[low];
    a[low] = a[j];
    a[j] = temp;
    qsort(low, j - 1);
    qsort(j + 1, high);
}

int main()
{
    cin>>n;
    int item;
    for(int i = 0 ; i < n ; i++)
    {
        cin>>item;
        a[i] = item;
    }
    qsort(0,n-1);
    for(int i = 0 ; i < n - 1 ; i++)
    {
        cout << a[i] << " ";
    }
    cout<<a[n-1]<<endl;
    return 0;
}

方法二代碼如下

void qsort(int l,int r)
{
    int mid=a[(l+r)/2];//基準(zhǔn)數(shù)
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//查找左半部分比中間數(shù)大的數(shù)，到mid就停止
        while(a[j]>mid) j--;//查找右半部分比中間數(shù)小的數(shù)，到mid就停止
        if(i<=j)//如果有一組不滿足排序條件（左小右大）的數(shù)，這里注意要有=
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }while(i<=j);//這里注意要有=
    if(l<j) qsort(l,j);
    if(i<r) qsort(i,r);
}