快速排序基础版及其小小的改进

Love The Way You Lie 2021-06-24 15:59 308阅读 0赞

基础版快速排序代码如下：

/*
     * 基本排序算法
     * */
    public class QuickSort {
    
    	private QuickSort(){}
    	
    	/*
    	 * 对arr[l, r]部分进行partition操作
    	 * 返回值p,使得arr[l, p-1] < arr[p], arr[p+1, r] > arr[p]
    	 * */
    	private static int partition(Comparable[] arr, int l, int r){
    		
    		Comparable v = arr[l];
    		
    		int j = l;		//arr[l+1, j] < v ; arr[j+1, i) > v
    		for(int i= l+1; i <= r; i++){
    			if(arr[i].compareTo(v) < 0){
    				swap(arr, ++j, i);
    			}
    		}
    		swap(arr, l, j);
    		return j;
    	}
    	
    	//递归使用快速排序，对arr[l, r]的范围进行排序
    	private static void sort(Comparable[] arr, int l, int r){
    		if(l >= r)
    			return ;
    		int p = partition(arr, l, r);
    		sort(arr, l, p-1);
    		sort(arr, p+1, r);
    	}
    	
    	public static void sort(Comparable[] arr){
    		int n = arr.length;
    		sort(arr, 0, n-1);
    	}
    	
    	private static void swap(Object[] arr, int i, int j){
    		Object t = arr[i];
    		arr[i] = arr[j];
    		arr[j] = t;
    	}
    	
    	public static Integer[] randomArray(int n, int min, int max) {
    		Integer[] arr = new Integer[n];
    		for(int i=0; i<n; i++)
    			arr[i] = new Integer((int)(Math.random() * (max - min + 1) + min));
    		return arr;
    	}
    	
    	public static void main(String[] args) {
    		int N = 1000000;
    		Integer[] a = randomArray(N, 0, 2000);
    		long startTime = System.currentTimeMillis();
    		sort(a);
    		long endTime = System.currentTimeMillis();
    		//SortHelper.printArray(a);
    		System.out.println("排序所用时间为:" + (endTime - startTime) + "ms");
    	}
    
    }

快速排序在处理一个巨大的无序数组时速度是非常快的，但是当其处理一个近乎有序的大数组时，其速度会大打折扣，在最差的情况下，他的算法复杂度甚至会退化到O(n^2)。导致其性能极速下降的原因如下：

在上面的代码中，我们每次取数组的第一个元素作为判断的基准点，在一个随机数组中没什么大问题，利用该基准点，我们每次可以将数组大致平均分为两个元素差不多的数组，然后再调用递归函数进行下一步的排序，其算法复杂度为O(nlogn).

然而处理一个近乎有序的数组时，我们每次取数组第一个元素作为基准点的话，该元素可能比后面的绝大部分元素小（或大），这样导致其算法复杂度会严重退化，性能大打折扣。在归并排序中，我们每次可以将数组平分为两个元素几乎相等的数组，所以在任何情况下，其算法复杂度可以保证为O(nlogn)，执行效率不会有太大的变化。

该算法的小优化如下：

在一个近乎有序的数组中，我们可以随机选择一个元素作为基准点，这样就可以大大降低其算法复杂度退化的可能性（选择出一个元素比其他n-1个元素小（或大）的可能性为1/n，再选出一个元素比其他元素小（或大）的可能性为1/(n-1)，以此类推，该算法复杂度退化为O(n^2)的可能性很小了）。而我们只需要改进partition()算法就可以了，代码如下：

private static int partition(Comparable[] arr, int l, int r){
           
            int k = (int)(Math.random()*(r-l+1)) + l;
            swap(arr, k, l);
            
            Comparable v = arr[l];
            
            int j = l;        //arr[l+1, j] < v ; arr[j+1, i) > v
            for(int i= l+1; i <= r; i++){
                if(arr[i].compareTo(v) < 0){
                    swap(arr, ++j, i);
                }
            }
            swap(arr, l, j);
            return j;
        }