快速排序及优化算法（三向切分的快速排序）

落日映苍穹つ 2022-09-26 00:20 193阅读 0赞

# 快速排序算法 #

快速排序应该是应用最广的排序算法了，快速排序引人入目的特点包括原地排序（只需要一个很小的辅助栈），并且将长度是N的数组排序所需的时间和NlgN成正比。另外，快速排序的内循环比大多数排序算法都要小很多，快排性能出色的一个原因就是不会像shell和merge排序一样在内循环进行元素的交换。  
快速排序是一种分治的排序算法，将一个数组分成两个子数组，将两部分独立的进行排序。快排和归并是互补的：归并排序是将数组分成两个数组分别排序，并将有序的子数组归并以将整个数组排序；快速排序是当两个子数组都有序时，整个数组就已经有序了，因此快速排序是先处理再递归（切分过程总是能够排定一个元素）。

public class Sortexample {
        public static void Qsort(int[] a){
            sort(a,0,a.length-1);
        }
        public static void sort(int[] a,int lo,int hi){
            if(hi <= lo) return;
            int j = partition(a,lo,hi);
            sort(a,lo,j-1);
            sort(a,j+1,hi);
    
        }
        //快速排序的切分
        public static int partition(int[] a,int lo,int hi){
            int i = lo,j = hi +1;
            int key = a[lo];//用于分割数组的关键字
            while(true){
                while(a[++i]<key) if(i==hi) break;
                while(a[--j]>key) if(j==lo) break;
                if(i >= j) break;
                int temp = a[i];
                a[i] = a[j];
                a[j] =temp;
            }
            int temp = a[j];
            a[j] = a[lo];
            a[lo] = temp;
            return j;
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            int[] a = new int[]{
       1,3,4,2,5,8,7,6};
            Sortexample.Qsort(a);
            for(int c : a){
                System.out.println(c);
            }
        }
    }

其处理过程如图：

![这里写图片描述][20160913154210768]

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想

# 快速排序算法的优化 #

## 切换到插入排序 ##

和大多数递归算法一样，改进快速排序性能的一个简单办法是基于以下两点：

*  对于小数组，快速排序比插入排序慢
 *  因为递归，快速排序的sort()方法在小数组中也会调用自己  
    因此，在小数组排序时切换到插入排序，对于上述sort()函数进行简单的修改即可达到目的，语句`if(hi<=lo) return;`替换成下面的语句来对小数组进行插入排序：

if(hi<=lo+M){
        Insertion.sort(a,lo,hi);
        return;
    }

转换参数的最佳值M一般是和系统相关的，一般5到15之间都会取得好的效果。

## 三向切分的快速排序 ##

快速排序什么时候不适用？元素重复率特别高的时候。  
如何优化？三向切分。前后各俩指针，总共四个指针。俩额外的指针指向跟待选元素相同的元素，最后全部置换到中间。  
三向切分的好处？重复率高的时候，避免相同元素来回交换，节省交换次数。对于包含大量重复元素的数组，这个算法将排序时间从线性对数级降到了线性级别。

![这里写图片描述][20160913154422894]

public int sort(int a[],int low,int high){  
        if(low < high){  
            int lt = low,i=low+1,gt = high;  
            int temp = a[low];  
            while(i <= gt){  
                if(a[i] < temp){  
                    sawp(a,lt++,i++);//进行交换
                }else if(a[i] > temp){  
                    sawp(a,i,gt--);  
                }else{  
                    i++;  
                }  
            }  
            sort(a,low,lt-1);  
            sort(a,gt+1,high);  
        }   
    }

三向切分最坏的情况就是所有的主键都不相同，当存在重复键的时候，它的性能就会比归并好得多。

[20160913154210768]: /images/20220717/b5c4c081bccd45678899d368681997f0.png
[20160913154422894]: /images/20220717/64fbaa52340f450085da9e7abd7fabed.png