一、快速排序基本思想
设无序数组a[low...high]，利用分治法快速排序的基本思想如下：
1）分解
在a[low...high]中任选一个记录作为基准pivot，以此基准将当前无序区划分为左、右两个较小的子区间a[low...pivotpos-1]和a[pivot+1...high]，并使左边子区间中所有数字a[i]均小于等于基准pivot，右边子区间中所有数字a[j]均大于等于pivot，而基准pivot则位于正确的位置pivotpos上，它无序参加后续的排序。
2）求解
通过递归调用快速排序对左、右子区间a[low...pivotpos-1]和a[pivotpos+1...high]快速排序。
3）组合
因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，“组合”步骤无需做什么，可看做是空操作。
二、快速排序算法QuickSort
代码如下：
qSort(int i ,int j, int []a){ if(i<j){ int q = partition(i, j, a); qSort(i, q-1, a); qSort(q+1, j, a); } }三、划分算法Partition
1.具体做法
第一步：（初始化）设置两个指针i和j，它们的初值分别为区间的下界和上界，即 i=low，i=high；选取无序区的第一个数字 a[i] 作为基准，并将它保存在变量 pivot中。
第二步：令 j 自high起向左扫描，直到找到第1个数字小于pivot，将 a[j] 移至 i 所指的位置上，这相当于 a[j] 和 a[i] 进行了交换，使小于基准的数字移到了基准右边；然后令 i 指针自 i+1 位置开始向右扫描，直到找到第1 个数字大于pivot，将 a[i] 移到 j 所指的位置上，这相当于交换了 a[i] 和 a[j]；接着令指针 j 自位置 j-1 开始向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至 i=j 时，i 便是基准pivot最终的位置，将 pivot 放在此位置上就完成了一次划分。
2.划分算法代码如下：
partition(int i, int j, int []a){ int pivot = a[i]; while(i<j){ while(j>i&&a[j]>=pivot) j--; if(i<j) a[i++] = a[j]; while(a[i]<=pivot && i<j) i++; if(i<j) a[j--] = a[i]; } a[i] = pivot; return i; }四、测试代码
package com.algorithm.program; public class QuickSort{ public static void main(String []args){ int []a = {72,6,57,88,60,42,83,73,48,85}; QuickSort quickSort = new QuickSort(); int i = 0; int j=a.length-1; quickSort.qSort(i, j, a); for(i = 0;i<a.length;i++){ System.out.println(a[i]); } } public void qSort(int i ,int j, int []a){ if(i<j){ int q = partition(i, j, a); qSort(i, q-1, a); qSort(q+1, j, a); } } public int partition(int i, int j, int []a){ int pivot = a[i]; while(i<j){ while(j>i&&a[j]>=pivot) j--; if(i<j) a[i++] = a[j]; while(a[i]<=pivot && i<j) i++; if(i<j) a[j--] = a[i]; } a[i] = pivot; return i; } }