快速排序

1. 快速排序
   • 快速排序是一个知名度极高的排序算法，其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。
   • 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
   • 快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
2. 算法描述

   • 从数列中挑出一个元素，称为"基准"（pivot），

   • 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

   • 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     

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)
           return;
       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;
   }

6. 适用场景
   • 快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。