Java快速排序(二)

向右看齐 2021-09-19 23:52 208阅读 0赞

**双路快速排序**

上一种快速排序会导致有大量重复键值的退化为时间复杂度为O（n^2）,如图

为此，我们可以将一般的快速排序改进为双路快速排序，如图。定义两个索引，从序列两边分别检索排序

**双路快速排序法基本思想**

arr\[l, ..., r\]，选定v = arr\[l\] 作为标定点， arr\[l, ..., i) <=v, i 索引所指元素与 v 比较，小于v, i 索引右移，即i++； arr(j, ..., r\] >=v, j 索引所指元素与 v 比较，大于v, j 索引左移，即j--； 如果前面两个条件不满足了，则交换 arr\[i\] 与 arr\[j\] 的值，i++, j--,继续以上比较; 最后当 i > j 时，交换 arr\[l\] 与 arr\[j\]的位置,完成排序。

**Java双路快速排序代码：**

package lianxi;
    
    public class QuickSort {
    
    	private QuickSort() {
    		
    	}
    	private static int   partition2(int[] arr,int l,int r) {
    		
    		int v=arr[l];
    		int i=l+1;int j=r;
    		while( true ) {
    			while(i<=r && arr[i]<v) i++;
    			while(j>=l+1&& arr[j]>v)j--;
    			if (i>j) break;
    			swap(arr,i,j);
    			i++;
    			j--;
    		}
    		swap(arr,l,j);
    		return  j;
    	}
    	
    	private static void swap(int[] arr,int i,int j) {
        	int t = arr[i];
    	    arr[i]= arr[j];
    	    arr[j]=t;
    	}
    	
    	private static void  sort(int[] arr, int l,int r) {
    		
    		if(l>=r)
    		return;
    		int p =partition2(arr,l,r);
    		
    		sort(arr,l,p-1);
    		sort(arr,p+1,r);
    	}
    	
    	public static void sort(int[] arr) {
    		int n=arr.length;
    		sort(arr,0,n-1);
    	}
    	
    	public static void main(String[] args) {
    		int[] arr = {2,4,3,1};
    		
    		QuickSort.sort(arr);
    		for(int i=0;i<arr.length;i++) {
    			System.out.println(arr[i]);
    		}
    		
    	}
    }
    复制代码

**总结**

双路快速排序利用两个索引从两边开始检索，避免了重复键值多的时候导致两边不平衡的情况，它的实现也并不难。