快速排序可以说是使用最广的排序算法了,主要的特点是基于原地排序(不需要使用辅助数组,节省空间);其实对于长度为N的数组使用快速排序时间复杂度为 NlogN;在前几篇也一起讨论了其他的排序算法,都没能够把这两个特点结合起来。
本文转载自微信公众号「贝塔学JAVA」,作者Silently9527。转载本文请联系贝塔学JAVA公众号。
本文已被Github仓库收录 https://github.com/silently9527/JavaCore
程序员常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin
完全开源的淘客项目:https://github.com/silently9527/mall-coupons-server
前言
快速排序可以说是使用最广的排序算法了,主要的特点是基于原地排序(不需要使用辅助数组,节省空间);其实对于长度为N的数组使用快速排序时间复杂度为 NlogN;在前几篇也一起讨论了其他的排序算法,都没能够把这两个特点结合起来。
快速排序思路
快速排序也是一种分治的排序算法,把数组划分为两个子数组,然后递归对子数组进行排序,最终保证整个数组有序。
算法思路:
- 随机选择一个切分元素,通常选择的是数组的第一个元素
- 从数组的左边开始扫描找出大于等于切分元素的值,从数组的右边开始扫描找出小于等于切分元素的值,交换这两个值
- 循环这个过程直到左右两个指针相遇,这样就排定了一个元素,保证了切分元素左边的值都是小于它的值,右边的元素都是大于它的值
- 递归这个过程,最终保证整个数组有序
算法实现
根据快速排序算法的思路,我们可以写出第一版实现:
- publicclassQuickSortimplementsSortTemplate{
- @Override
- publicvoidsort(Comparable[]array){
- quickSort(array,0,array.length-1);
- }
- privatevoidquickSort(Comparable[]array,intlo,inthi){
- if(lo>=hi){
- return;
- }
- intpartition=partition(array,lo,hi);
- quickSort(array,lo,partition-1);
- quickSort(array,partition+1,hi);
- }
- privateintpartition(Comparable[]array,intlo,inthi){
- inti=lo,j=hi+1;
- Comparableel=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);
- returnj;
- }
- }
这段代码是实现快速排序的常规实现,考虑最糟糕的情况,假如需要排序的数组是已经有序的[1,2,3,4,5,6,7,8],执行快速排序的过程如图:
对一个长度为N的数组,最糟糕的情况下需要递归N-1次,所以时间复杂度是O(n2),为了避免这种情况出现,我们来看下算法如何改进
算法改进
- 保证随机性 为了避免最糟糕的情况出现,有两个办法,第一是在排序数组之前先随机打乱数组;第二是在partition方法中随机取切分元素,而不是固定取第一个,简单实现:
- privateintpartition(Comparable[]array,intlo,inthi){
- inti=lo,j=hi+1;
- intrandom=newRandom().nextInt(hi-lo)+lo;
- exch(array,lo,random);
- Comparableel=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);
- returnj;
- }
- 切换到插入排序 这点和归并排序一样,对于小数组的排序直接切换成插入排序
- privatevoidquickSort(Comparable[]array,intlo,inthi){
- if(lo>=hi){
- return;
- }
- if(hi-lo<5){//测试,小于5就切换到插入排序
- insertionSort(array,lo,hi);
- return;
- }
- intpartition=partition(array,lo,hi);
- quickSort(array,lo,partition-1);
- quickSort(array,partition+1,hi);
- }
- //插入排序
- privatevoidinsertionSort(Comparable[]array,intlo,inthi){
- for(inti=lo;i<=hi;i++){
- for(intj=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++
代码实现:
- publicclassQuick3waySortimplementsSortTemplate{
- @Override
- publicvoidsort(Comparable[]array){
- quickSort(array,0,array.length-1);
- }
- @SuppressWarnings("unchecked")
- privatevoidquickSort(Comparable[]array,intlo,inthi){
- if(lo>=hi){
- return;
- }
- intlt=lo,i=lo+1,gt=hi;
- Comparableel=array[lo];
- while(i<=gt){
- inttmp=el.compareTo(array[i]);
- if(tmp>0){
- exch(array,lt++,i++);
- }elseif(tmp<0){
- exch(array,i,gt--);
- }else{
- i++;
- }
- }
- quickSort(array,lo,lt-1);
- quickSort(array,gt+1,hi);
- }
- }
知优网 » 快速排序算法实现及优化(快速排序算法实现及优化策略)