快速排序-学习笔记

快速排序的思想：首先是在待排序数组中的第一个元素选为基准数（也可以随机选取），然后进行左右的交替扫描，

过程是这样的：先是从左向右扫描（也可以先从右向左扫描），当遇到一个数比基准数小时，则把这个数与基准数交换位置，因为是第一遍扫描，所以要与基准数交换位置，然后从右向左扫描，当遇到一个数比基准数大时，则把这个数赋值到之前与基准数交换位置的数上，这样扫描一遍，以基准数为分界点，左边的都比它小，右边的都比它大，然后再分成两个数组，不包括基准数，重复上述步骤，直到排好序。快速排序是不稳定排序

代码如下：

#include

void QuickSort(int a[],int left,int right)
{
    int temp=a[left],l=left,r=right;//取数组第一个数为基准数
    if(l//控制递归深度，最少有两个待排序数
    {
        while(l!=r) //当l和r相等时退出循环
        {
            while(r>l&&a[r]>=temp)//如果右面的数比基准数大时，继续向左扫描
            {
                r--;
            }
            a[l]=a[r];//此时右边的数比基准数小，左右交换位置
            while(r>l&&a[l]<=temp)//如果左边的数比基准数小时，继续向右扫描
            {
                l++;
            }
            a[r]=a[l];//此时左边的数比基准数大，左右交换位置
        }
        a[r]=temp;//此时r和l是相等的，把基准数落赋值回去；
        QuickSort(a,left,r-1);//对基准数左边的进行递归排序
        QuickSort(a,l+1,right);//对基准数右边的进行递归排序
    }
}
int main()
{
    int a[20],n;
    scanf("%d",&n);
    for(int i=0; i)
    {
        scanf("%d",&a[i]);
    }
    QuickSort(a,0,n-1);
    for(int i=0; i)
    {
        printf("%d ",a[i]);
    }
}