1 基本思想 快速排序是在冒泡排序的基础上改进而来的，它是基于分治的思想。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使得整个数据变成有序序列。
2，算法的实现(Java)
package Algorithm; public class QuickSort { /** * @param args */ public static void main(String[] args) { int[] data = new int[] {11,10,55,78,100,111,45,56,79,90,345,1000}; System.out.println("排序之前："); QuickSort.output(data); System.out.println(); System.out.println("排序之后："); QuickSort.qsort(data,0,data.length-1); QuickSort.output(data); } public static void qsort(int[] arr, int left, int right){ if(left < right){ int index = partition(arr,left,right);//讲数组分成两部分 qsort(arr,left,index-1);//递归排序左子数组 qsort(arr,index+1,right);//递归排序右子数组 } } private static int partition(int[] arr, int left, int right) { int key = arr[left];//设置关键数key为要排序数组的第一个元素 while(left<right){ while(left<right&&arr[right]>=key) --right; arr[left] = arr[right];//交换比key小的记录到左侧 while(left<right&&arr[left]<=key) left++; arr[right] = arr[left];//交换比key小的记录到右侧 } arr[left] = key; return left;//返回划分中间点，即，key右边的数全部比key大，key左边的数全部比key小 } //输出打印 public static void output(int[] arr){ for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+"\t"); } } }最终结果显示如下：
3 性能分析 快速排序的效率与划分是否对称有关，而后者又与选择哪一个元素进行划分有关。最坏情况下，时间复杂度为O(n^2)，此时两个区域分别包含n-1个元素和0个元素。最好的情况下，时间复杂度为O(nlog2n)。由于快速排序是递归的，需要一个栈来存放每一层递归调用的必要信息，最大容量与递归调用的深度一致。空间复杂度最好的情况为O(log2n),最坏的情况为O(n)。平均情况下，为O(log2n)。它是一种不稳定的排序。
