Sorting｜快速排序

思想

在待排序序列 \((k_s,k_{s+1},...,k_t)\) 中任意选择一个元素作为分界，将比它小的移至其左，比它大的移至其右，这样该元素就在它排好序的位置上。

过程

合理性：在任何时刻，l的左边都是比key小的元素，r的右边都是比key大的元素

演示

code

递归，quickSort函数实现对一段序列进行快排

void swap(int a[],int i,int j)
{
    int temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void quickSort(int a[],int left,int right)        //调用时：quickSort(a,0,n-1)
{
    if(left>=right)
        return;
    int i,j,key;
    i=left;
    j=right;
    key=a[left];
    while(i<j)
    {
        while(i<j && a[j]>=key)  //从右向左扫描，找到比key小的元素
            j--;
        a[i]=a[j];      //赋给i指向的位置
        while(i<j && a[i]<=key)
            i++;
        a[j]=a[i];
    }
    a[i]=key;
    quickSort(a,left,i-1);     //对左半序列进行快排
    quickSort(a,i+1,right);    //对右半序列进行快排
}