快速排序：通过一趟排序将待排记录分割成独立的两部分，
其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列的目的

  1. /** 
  2. * @Description: 快速排序：通过一趟排序将待排记录分割成独立的两部分， 
  3. * 其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列的目的 
  4. * @Author: lizhouwei 
  5. * @CreateDate: 2018/6/23 16:56 
  6. */
  7. public class QuickSort {
  9.     public static void quickSort(Integer[] arr) {
  10.         if (arr == null || arr.length == 0) {
  11.             return;
  12.         }
  13.         SortUtil.printArray("快速排序前", arr);
  14.         quickSort(arr, 0, arr.length - 1);
  15.         SortUtil.printArray("快速排序后", arr);
  16.     }
  18.     private static void quickSort(Integer[] arr, int left, int right) {
  19.         if (left < right) {
  20.             int pivot = partition(arr, left, right);
  21.             quickSort(arr, left, pivot - 1);
  22.             quickSort(arr, pivot + 1, right);
  23.         }
  24.     }
  26.     private static int partition(Integer[] arr, int left, int right) {
  27.         int pivot = (left + right) / 2;
  28.         if (arr[pivot] < arr[left] && arr[pivot] < arr[right]) {
  29.             if (arr[left] < arr[right]) {
  30.                 pivot = left;
  31.             } else {
  32.                 pivot = right;
  33.             }
  34.         }
  35.         if (arr[pivot] > arr[left] && arr[pivot] > arr[right]) {
  36.             if (arr[left] < arr[right]) {
  37.                 pivot = right;
  38.             } else {
  39.                 pivot = left;
  40.             }
  41.         }
  42.         if (pivot != right) {
  43.             SortUtil.swap(arr, pivot, right);
  44.         }
  45.         int j = 0;
  46.         for (int i = 0; i < right; i++) {
  47.             if (arr[i] <= arr[right]) {
  48.                 SortUtil.swap(arr, i, j++);
  49.             }
  50.         }
  51.         SortUtil.swap(arr, right, j++);
  52.         return j;
  53.     }
  54. }

快速排序基准点优化

对于基准点的优化一般有三种：固定切分，随机切分和三数取中法。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N^2)。对于三数取中选择基准点是最理想的一种。

快速排序算法的时间复杂度

10.1最优情况下
快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；
此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；
下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
T[n] = 2T[n/2] + n ————————第一次递归
令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ————————第二次递归
= 2^2 T[ n/ (2^2) ] + 2n
令：n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n ————————第三次递归
= 2^3 T[ n/ (2^3) ] + 3n
…
令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ————————第m次递归(m次后结束)
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
T[n] = 2^m T[1] + mn ；其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数
又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；
综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )
10.2最差情况下
最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )
10.3平均时间复杂度
快速排序的平均时间复杂度是：O(nlogn)

快速排序的稳定性

因为在快速排序的时候，即使待排序元素可基数相等也需要移动待排序元素的位置使得有序，所以快速排序是不稳定的

快速排序与其他排序的比较

快速排序 - 图2