快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。
一次快速排序详细过程： 选择数组第一个值作为枢轴值。
代码实现：package QuickSort;public class QuickSortRealize {(int[] arr){QSort(arr,0,arr.length-1);}(int[] arr,int low,int high){int pivot;if(low<high){pivot = Partition(arr,low,high);//将数组子序列一分为二QSort(arr, low, pivot-1);//对低子表递归排序QSort(arr, pivot+1, high);//对高子表递归排序}}(int[] arr,int low,int high){if(arr == null || low<0 || high>=arr.length){new Exception();}int pivotkey;pivotkey = arr[low];//选取第一个记录作枢轴记录while(low<high)//从表的两端向中间扫描{while(low<high && arr[high]>=pivotkey){//如果大于枢轴值，则下标减一，否则，跳出循环。high–;}Swap(arr, low, high);//交换while (low<high && arr[low]<pivotkey){//如果小于枢轴值，则下标加一，否则，跳出循环。low++;}Swap(arr, low, high);//交换}return low;}(int[] arr,int low,int high){int temp = arr[low];arr[low] = arr[high];arr[high] = temp;}(String[] args) {int[] arr = {50,10,90,30,70,40,80,60,20};QuickSort(arr);for (int array : arr) {System.out.print(array+” “);}System.out.println();}}
快速排序的时间性能取决于快速排序递归的深度，可以用递归数来描述算法的执行情况。如果递归树是平衡的，那么此时的性能也是最好的。 也就是说，在最优的情况下，快速排序算法的时间复杂度为 O(nlogn)。
就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度log2n ，其空间复杂度也就为 O(logn) ，最坏情况，需要进行递归调用，其空间复杂度为 O(n)，平均情况 空间复杂度也为 (logn)。 可惜的是 关键字的比较和交换是跳跃进行的，因此，快速排序是 种不稳 定的排序方法。
优化算法：1、优化选取枢轴
三数取中，即取三个关键字先进行排序，将中间数作为枢轴， 一般是取左端、右端和中间三个数， 也可以随机选取。 对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivo tkey， 因此还有个办法是所谓的九数取中，先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴 。
package QuickSort;public class QuickSortRealize {(int[] arr){QSort(arr,0,arr.length-1);}(int[] arr,int low,int high){int pivot;if(low<high){pivot = Partition(arr,low,high);//将数组子序列一分为二QSort(arr, low, pivot-1);//对低子表递归排序QSort(arr, pivot+1, high);//对高子表递归排序}}(int[] arr,int low,int high){if(arr == null || low<0 || high>=arr.length){new Exception();}int pivotkey;ChoosePivotkey(arr,low,high);//选取枢轴值pivotkey = arr[low];while(low<high)//从表的两端向中间扫描{while(low<high && arr[high]>=pivotkey){//如果大于枢轴值，则下标减一，否则，跳出循环。high–;}Swap(arr, low, high);//交换while (low<high && arr[low]<pivotkey){//如果小于枢轴值，则下标加一，否则，跳出循环。low++;}Swap(arr, low, high);//交换}return low;}(int[] arr,int low,int high){int temp = arr[low];arr[low] = arr[high];arr[high] = temp;}(int[] arr,int low,int high){int mid = low + (int)(high-low)/2;if(arr[low]>arr[high]){//保证左端较小Swap(arr, low, high);}if(arr[mid]>arr[high]){//保证中间较小Swap(arr, mid, high);}//此时最大值在最右边if(arr[mid]>arr[low]){//保证中间较小Swap(arr, mid, low);}}(String[] args) {int[] arr = {50,10,90,30,70,40,80,60,20};QuickSort(arr);for (int array : arr) {System.out.print(array+” “);}System.out.println();}}2、优化不必要的交换爱的力量大到可以使人忘记一切，
