排序算法篇（快速排序）

1、算法概念。

快速排序（Quicksort）是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。

2、算法思想。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3、实现思路。

①以第一个关键字K1为控制字，将[K1,K2,…,Kn]分成两个子区，使左区所有关键字小于等于K1，右区所有关键字大于等于K1，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。

②把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归）

③重复第①、②步，直到左区处理完毕。

Java实现代码：

/**

*description:快速排序

*@autorkwzhang

*modify:2012-6-20

*

*@parampData

*@paramleft

*@paramright

*@return

*/

staticvoidquicksort(intn[],intleft,intright){

intdp;

if(left<right){

dp=partition(n,left,right);

quicksort(n,left,dp-1);

quicksort(n,dp+1,right);

}

}

staticintpartition(intn[],intleft,intright){

intpivot=n[left];

while(left<right){

while(left<right&&n[right]>=pivot)

right--;

if(left<right)

n[left++]=n[right];

while(left<right&&n[left]<=pivot)

left++;

if(left<right)

n[right--]=n[left];

}

n[left]=pivot;

returnleft;

}