快速排序

通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的记录的关键字小，然后分别对这两部分记录继续按照这一过程排序

算法过程

1. 先设定一个分界值（枢纽/哨兵），通过该值将数组分为左右两个部分
2. 将小于分界值的放左边，将大于分界值的放右边
3. 然后对左边和右边重复1和2的排序过程，直至数组不可分，则整个数组达到有序状体

算法评价

• 算法的时间复杂度为$O(nlogn)$
• 其是一种不稳定的算法，是对冒泡排序的一种改进

算法实现

源代码：

#include <iostream>
using namespace std;
void swap(int *arr,int low,int high){
    int tmp;
    tmp=arr[low];
    arr[low]=arr[high];
    arr[high]=tmp;
}
int partition(int *arr,int low,int high){
    int piv;
    piv=arr[low];
    while(low<high){
        while(low<high&&arr[high]>piv)high--;
        swap(arr,low,high);
        while(low<high&&arr[low]<piv)low++;
        swap(arr,low,high);
    }
    return low;
}
void qsort(int *arr,int low,int high){
    int piv;
    if(low<high){
        piv=partition(arr,low,high);
        qsort(arr,low,piv-1);
        qsort(arr,piv+1,high);
    }
}
void quicksort(int *arr,int len){
    qsort(arr,0,len);
}
int main(){
    int arr[]={9,1,5,8,3,7,4,6,2},len=9;
    cout<<"排序前顺序："<<endl;
    for(int i=0;i<9;i++)cout<<arr[i];
    quicksort(arr,len-1);
    cout<<"\n排序后顺序："<<endl;
    for(int i=0;i<9;i++)cout<<arr[i];
    return 0;
}

运行结果：

排序前顺序：
915837462
排序后顺序：
123456789