快速排序算法实现及优化

本文转载自微信公众号「贝塔学JAVA」，快速作者Silently9527。排序转载本文请联系贝塔学JAVA公众号。算法实现

本文已被Github仓库收录 https://github.com/silently9527/JavaCore

程序员常用的及优IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin

完全开源的淘客项目：https://github.com/silently9527/mall-coupons-server

前言

快速排序可以说是使用最广的排序算法了，主要的快速特点是基于原地排序(不需要使用辅助数组，节省空间);其实对于长度为N的排序数组使用快速排序时间复杂度为 NlogN;在前几篇也一起讨论了其他的排序算法，都没能够把这两个特点结合起来。算法实现

快速排序思路

快速排序也是及优一种分治的排序算法，把数组划分为两个子数组，快速然后递归对子数组进行排序，排序最终保证整个数组有序。算法实现

算法思路：

随机选择一个切分元素，及优通常选择的快速是数组的第一个元素 从数组的左边开始扫描找出大于等于切分元素的值，从数组的排序右边开始扫描找出小于等于切分元素的值，亿华云计算交换这两个值 循环这个过程直到左右两个指针相遇，算法实现这样就排定了一个元素，保证了切分元素左边的值都是小于它的值，右边的元素都是大于它的值 递归这个过程，最终保证整个数组有序

算法实现

根据快速排序算法的思路，我们可以写出第一版实现：

public class QuickSort implements SortTemplate {      @Override     public void sort(Comparable[] array) {          quickSort(array, 0, array.length - 1);     }     private void quickSort(Comparable[] array, int lo, int hi) {          if (lo >= hi) {              return;         }         int partition = partition(array, lo, hi);         quickSort(array, lo, partition - 1);         quickSort(array, partition + 1, hi);     }     private int partition(Comparable[] array, int lo, int hi) {          int i = lo, j = hi + 1;         Comparable el = array[lo];         while (true) {              while (less(array[++i], el)) {                  if (i == hi) {                      break;                 }             }             while (less(el, array[--j])) {                  if (j == lo) {                      break;                 }             }             if (i >= j) {                  break;             }             exch(array, i, j);         }         exch(array, lo, j);         return j;     } } 

这段代码是实现快速排序的常规实现，考虑最糟糕的情况，假如需要排序的数组是已经有序的[1,2,3,4,5,6,7,8]，执行快速排序的过程如图：

对一个长度为N的数组，最糟糕的情况下需要递归N-1次，所以时间复杂度是O(n2)，为了避免这种情况出现，我们来看下算法如何改进

算法改进

保证随机性 为了避免最糟糕的服务器托管情况出现，有两个办法，第一是在排序数组之前先随机打乱数组;第二是在partition方法中随机取切分元素，而不是固定取第一个，简单实现： private int partition(Comparable[] array, int lo, int hi) {      int i = lo, j = hi + 1;     int random = new Random().nextInt(hi - lo) + lo;     exch(array, lo, random);     Comparable el = array[lo];     while (true) {          while (less(array[++i], el)) {              if (i == hi) {                  break;             }         }         while (less(el, array[--j])) {              if (j == lo) {                  break;             }         }         if (i >= j) {              break;         }         exch(array, i, j);     }     exch(array, lo, j);     return j; }  切换到插入排序 这点和归并排序一样，对于小数组的排序直接切换成插入排序 private void quickSort(Comparable[] array, int lo, int hi) {      if (lo >= hi) {          return;     }     if (hi - lo < 5) {   //测试，小于5就切换到插入排序         insertionSort(array, lo, hi);         return;     }     int partition = partition(array, lo, hi);     quickSort(array, lo, partition - 1);     quickSort(array, partition + 1, hi); } //插入排序 private void insertionSort(Comparable[] array, int lo, int hi) {      for (int i = lo; i <= hi; i++) {          for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {              exch(array, j, j - 1);         }     } } 

三向切分 当我们需要排序的数组中出现了大量的重复元素，我们实现的快速排序在递归的时候会遇到许多全部重复的子数组，我们的算法依然会对其进行切分，这里有很大的提升空间。

思路就是先随意选择一个切分元素(el)，然后把数组切换成大于、等于、小于三个部分，一次递归可以排定所有等于切分元素的值;维护一个指针lt、gt，使得a[lo..lt-1]都小于切分元素，站群服务器a[gt+1..hi]都大于切分元素;

初始化变量：lt=lo, i=lo+1, gt=hi if a[i] < el ; 交换a[i]与a[lt], i++, lt++ if a[i] > el ; 交换a[gt]与a[i], gt-- a[i] == el; i++

代码实现：

public class Quick3waySort implements SortTemplate {      @Override     public void sort(Comparable[] array) {          quickSort(array, 0, array.length - 1);     }     @SuppressWarnings("unchecked")     private void quickSort(Comparable[] array, int lo, int hi) {          if (lo >= hi) {              return;         }         int lt = lo, i = lo + 1, gt = hi;         Comparable el = array[lo];         while (i <= gt) {              int tmp = el.compareTo(array[i]);             if (tmp > 0) {                  exch(array, lt++, i++);             } else if (tmp < 0) {                  exch(array, i, gt--);             } else {                  i++;             }         }         quickSort(array, lo, lt - 1);         quickSort(array, gt + 1, hi);     } } 

很赞哦!（8883）