快速排序作为一种高效的排序算法被广泛应用SUN的JDK中的Arrayssort 方法用的就是快排
快排采用了经典的分治思想（divide and conquer）
Divide选取一个基元X（一般选取数组第一个元素）通过某种分区操作（partitioning）将数组划分为两个部分左半部分小于等于X右半部分大于等于X
Conquer 左右两个子数组递归地调用Divide过程
Combine快排作为就地排序算法（in place sort）不需要任何合并操作
可以看出快排的核心部分就是划分过程（partitioning）下面以一个实例来详细解释如何划分数组（图取自于《算法导论》）
初始化选取基元P=就是数组首元素i=j=i+= (数组下标以开头)
循环不变量~i之间的元素都小于或等于Pi+~j之间的元素都大于或等于P
循环过程j 从到n考察j位置的元素如果大于等于P就继续循环如果小于P就将j位置的元素（不应该出现在i+~j这个区间）和i+位置(交换之后仍在 i+~j区间)的元素交换位置同时将i+这样就维持了循环不变量（见上述循环不变量说明）直到j=n完成最后一次循环操作
要注意的是在完成循环后还需要将i位置的元素和数组首元素交换以满足我们最先设定的要求（对应图中的第i步）
细 心的读者可能会想到另一种更直白的分区方法即将基元取出存在另一相同大小数组中遇到比基元小的元素就存储在数组左半部分遇到比基元大的元素就存储在 数组右半部分这样的操作复杂度也是线性的即Theta(n)但是空间复杂度提高了一倍这也是快排就地排序的优势所在
复制代码 代码如下:
public class QuickSort {
private static void QuickSort(int[] arrayint startint end)
{
if(start<end)
{
int key=array[start];//初始化保存基元
int i=startj;//初始化ij
for(j=start+;j<=end;j++)
if(array[j]<key)//如果此处元素小于基元则把此元素和i+处元素交换并将i加如大于或等于基元则继续循环
{
int temp=array[j];
array[j]=array[i+];
array[i+]=temp;
i++;
}
}
array[start]=array[i];//交换i处元素和基元
array[i]=key;
QuickSort(array start i);//递归调用
QuickSort(array i+ end);
}
}
public static void main(String[] args)
{
int[] array=new int[]{};
QuickSort(array arraylength);
for(int i=;i<arraylength;i++)
{
Systemoutprintln((i+)+"th:"+array[i]);
}
}
}
