快速排序是极为优秀的排序算法，下面对该算法进行详细的计算。 算法基本思路： 快速排序一般基于递归实现。其思路是这样的： 1.选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。 2.基于“枢轴”(pivot)值，将数组分为两部分，较小的分在左边，较大的分在右边。 3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。 4.对两个子数组分别重复上述过程，直到每个数组只有一个元素。 5.排序完成。 下面是快速排序的示意图（图片来自维基百科）： 代码实现
public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1); } private static void qsort(int[] arr, int low, int high){ if (low < high){ int pivot=partition(arr, low, high); //将数组分为两部分 qsort(arr, low, pivot-1); //递归排序左子数组 qsort(arr, pivot+1, high); //递归排序右子数组 } } private static int partition(int[] arr, int low, int high){ int pivot = arr[low]; //枢轴记录 while (low<high){ while (low<high && arr[high]>=pivot) --high; arr[low]=arr[high]; //交换比枢轴小的记录到左端 while (low<high && arr[low]<=pivot) ++low; arr[high] = arr[low]; //交换比枢轴小的记录到右端 } //扫描完成，枢轴到位 arr[low] = pivot; //返回的是枢轴的位置 return low; }算法的复杂度的分析 对程序进行分析，每一次调用partition()方法都需要扫描一遍数组长度（注意，在递归的时候这个长度并不是原数组的长度n，而是被分隔出来的小数组，即n*(2^(-i))），其中i为调用深度。而在这一层同样长度的数组有2^i个。那么，每层排序大约需要O(n)复杂度。而一个长度为n的数组，调用深度最多为log(n)层。二者相乘，得到快速排序的平均复杂度为O(n ㏒n)。
通常，快速排序被认为是在所有同数量级的排序方法中，平均性能最好。
从代码中可以很容易地看出，快速排序单个栈的空间复杂度不高，每次调用partition方法时，其额外开销只有O(1)。所以，最好情形下快速排序空间复杂度大约为O(㏒n)。
