基本思想
 

    冒泡排序的一种改进。通过一趟排序将待排记录分割成独立的两部分，其中一部分关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法原理


    使用分治策略，将一个序列分为两个子序列。

    步骤：

在待排序的n个记录中任选一个进行记录（通常选第一个），作为为基准（分区标准）。
进行分区，即：将所有比基准值小的元素放在基准左边，所有比基准值大的元素放在基准的右边，中间为所选的基准。

对左右两个分区递归进行步骤1、2，递归结束条件是序列的大小是0或1。

特点
 

 数据结构：数组

 稳定性：不稳定

 

过程
  

     

                宏观过程

 

复杂度与辅助空间
 

 最差时间复杂度：O(n^2)

 最优时间复杂度：O(nlog2n)

 平均时间复杂度：O(nlgn)

 所需辅助空间：O(log2n)~O(n)

 

源程序

void quickSort(int a[],int low, int high)//a:待排序数组，low:最低位的下标，high:最高位的下标
{
    int left=low,right=high;
    int key=a[left];//用数组的第一个记录作为分区元素
    
    if(low>=high)
        return;
    while(left!=right){
        while(left<right&&a[right]>=key)//从右向左扫描，找第一个码值小于key的记录，并交换到key
            right--;
        a[left]=a[right];
        while(left<right&&a[left]<=key)//从左向右扫描，找第一个码值大于key的记录，并交换到右边
            left++;
        a[right]=a[left];    
    }
    a[left]=key;//分区元素放到正确位置
    quickSort(a,low,left-1);
    quickSort(a,left+1,high);
}