快速排序

这里我们直接开始讲相对的最优解 带随机数的三路快排 好了，中间还有很多版本的快排，但是都有一些问题导致在某种极端情况下造成耗费时间极多。

  • 基础快排：在序列本身有序的情况下复杂度为O（n²）

  • 带随机数的快排：在序列本身有序的情况下复杂度为O（nlogn），但是在序列全部元素相同情况下复杂度为O（n²）

  • 带随机数的双路快排：比前者更快一些为O（n），因为前后同时向中间遍历，但是在序列全部元素相同情况下的复杂度问题仍旧未解决

  • 带随机数的三路快排： 解决上述各种问题且时间复杂度最快O（n）

工作原理：

将数组分为三个部分，小于V的，等于V的，大于V的。

  1. 首先在数组中选取任意一个下标和最左边的下标互换（选取一个随机下标的目的是，将快排结果最后V左边或右边没有东西的极端情况概率降到最小甚至约等于0，如果出现这种情况将会导致复杂度为n²，这里我们不再深入讨论）

  2. 确定需要的变量：因此我们要有2个下标 Lt，Rt 将数组分割成3部分。还需要一个下标 i 指向当前的元素 e 。除此之外，用 l 和 r 确定数组的首尾。

  3. 分配当前元素 e 去哪个区域 这里我们又分为3种情况：

    1. e < V 将e和Lt+1处(也就是 ==V 的第一个元素)的位置交换，然后Lt++

    2. e == V 将e直接纳入该区域（也就是不做处理）然后 i++ 即可

    3. e > V 将e和Rt – 1处(也就是 >V 的前一个元素)的位置交换，然后Rt–

    无论是哪个情况，无非就是将其和Lt和Rt附近的元素交换位置即可。

  1. 那么当全部都排序完毕时，也就是鼠标指的那个点处，i 和 Rt 重合时，退出循环

  1. 因为按顺序应该是 小于V ，V，==V，>V ，所以只要将V和 <V 处的最后一个元素交换位置即可

6.最后反复递归调用 V 的区间，从而让两边的区间也都有序。

实现一下吧：

package com.sort;import java.util.Random;​/** * @Author: 翰林猿 * @Description: 三路快排 **/public class Quick {  public Quick() {   }​  public static <T extends Comparable> void quicksort(T[] arr) {    Random random = new Random();    quicksort3ways(arr, 0, arr.length - 1, random);   }​  private static <T extends Comparable> void quicksort3ways(T[] arr, int l, int r, Random random) {    if (l >= r)      return;    int randomInt = random.nextInt(r + 1 - l);   //生成一个不超过数组长度的随机数    swap(arr, randomInt, l);                 //把他和首元素交换位置    //定义需要的变量    int Lt = l;    int Rt = r + 1;    int i = Lt + 1;    while (i < Rt) {      if (arr[i].compareTo(arr[l])  0) {        Rt--;                //因为应该交换Rt-1处，所以可以直接先--再交换        swap(arr, Rt , i);        i++;       }     }    swap(arr,l,Lt);               //将V摆到小于V和等于V中间    quicksort3ways(arr,l,Lt-1,random);    //反复递归调用 V 的区间，让这两区间也都有序    quicksort3ways(arr,Rt,r,random);   }​  public static  void swap(E[] arr, int j, int beforej) {    E t = arr[j];    arr[j] = arr[beforej];    arr[beforej] = t;   }}​