前言
快速排序可以说是使用最广泛的排序算法。 主要特点是基于原地排序(不需要使用辅助数组，节省空间)。 其实对于长度n的数组使用高速排序时间复杂度NlogN； 前几篇文章还讨论了其他的排序算法，但无法将这两个特征结合起来。
快速排序思路
快速排序也是将数组分割为两个子数组，递归地对子数组进行排序，最终保证数组整体秩序的分布式排序算法。算法思路：
随机选择分割元素。 通常，数组的第一个元素从数组的左侧扫描，以查找大于等于分区元素的值，从数组的右侧扫描，以查找小于等于分区元素的值。 更换这个过程直到左右指针相遇。 这样可以确保分割元素的左侧值小于或等于该值，右侧元素以大于或等于该值的值递归处理，从而最终确保整个数组在
算法实现
之间的速度更快publicclassquicksortimplementssorttemplate {
@Override
公共语音排序(比较阵列)。
快速排序(阵列，0，阵列长度-1)；
}
比较阵列、内部、内部) {
if (低=高) {
返回；
}
int partition=partition (阵列，低，高)；
快速排序(阵列、低、分区-1)；
快速排序(阵列，分区1，高)；
}
私有分区(比较阵列、内部、内部)
inti=lo，j=hi 1；
comparable El=阵列；
威廉(真)。
wile (less (阵列，电致发光) ) )
if(I==hi高) {
布莱克；
}
}
while (less (电子阵列[-- j ] ) ) ) ) 0
if(j==lo ) {
布莱克；
}
}
if(I=j ) {
布莱克；
}
exch (阵列，I，j )；
}
exch (阵列，lo，j )；
返回；
}
}
其中，exch、less方法的实现请参阅前面的文章《常见的初级排序算法，这次全搞懂》
此代码是实现快速排序的常规实现，请考虑最坏的情况。 如果需要排序的数组已经排序[1、2、3、4、5、6、7、8]，则执行快速排序的过程如下所示：
在长度为n的数组中，最坏的情况下需要递归N-1次，所以时间的复杂度为o(n )。 为了避免这种情况，让我们看看算法是如何改进的
算法改进
为了避免保证随机性的最坏情况，有两种方法。 第一，在排序数组之前随机打乱数组。 第二，不是固定地取第一个，而是通过用partition方法随机取分割要素，很容易实现。 私人分区(比较阵列，内部，内部) )。inti=lo，j=hi 1；
int random=新随机() .下一个(HI-lo ) LO；
exch (阵列、发光、随机)；
比较电子工程师=a
rray[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=hiif 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); } }最后（点关注，不迷路）
文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。
最后，「写作不易，请不要白嫖我哟」，希望朋友们可以「点赞评论关注」三连，因为这些就是我分享的全部动力来源
❝
有需要的朋友回复「源码」或私信发送「源码」
❞
精美的淘客项目完全开源啦，有需要的朋友回复「源码」或私信发送「源码」