快速排序的实现与分析

本是古典何须时尚 2022-04-22 02:14 165阅读 0赞

快速排序应用极广，效率极高且实现简单。快排和归并排序一样用到了分治的思想。

快排中，最关键的操作叫做“切分”，切分使得切分元素v左边的元素都不大于v，v右边的元素都不小于v。

设有数组a\[lo......hi\], lo、hi分别为数组的下界和上界，可以假设每次切分出来的元素下标为j，那么切分操作就返回j的值。那么以j为界，又可以将\[lo........(j-1)\]，\[(j+1)......hi\]两个子数组再次切分，直到整个a有序。

我们可以指定a\[lo\]为切分元素v，然后通过数组元素的比较和移动把v放在合适的位置以保证“切分元素v左边的元素都不大于v，v右边的元素都不小于v”这一基本条件。在比较和移动的过程中，我们设置了两个指针i和j，初始化i指向lo，j指向hi。然后开始第一次扫描，i从lo开始向hi走，当遇见大于v的元素时停下并指向该元素a\[i\]，与此同时，j从hi向lo走，当遇见小于v的元素时停下并指向该元素a\[j\]。此时a\[i\]>v，a\[j\]<v，为了保证切分的基本条件，所以将a\[i\]和a\[j\]交换位置。接下来继续上述操作，直到i>=j时（指针相遇）停止扫描，此时交换a\[lo\]和a\[j\]，便完成了一次切分操作。

递归地完成上述切分操作便能实现快速排序。

看一个例子：

int \[\]a=\{15, 7, 6, 29, 18, 24, -6, -20, 53, 47\};

第一次切分（i红，j蓝）：

v=a\[lo\]=15

15 7 6 29 18 24 -6 \-20 53 47，swap(a, i, j): 15 7 6 \-20 18 24 -6 29 53 47，此时i=3，j=7

15 7 6 -20 18 24 \-6 29 53 47，swap(a, i, j): 15 7 6 -20 \-6 24 18 29 53 47，此时i=4，j=6

15 7 6 -20 \-6 24 18 29 53 47，swap(a, lo, j): -6 7 6 -20 15 24 18 29 53 47，此时i=5, j=4

完成切分： -6 7 6 -20 15 24 18 29 53 47，可以发现，15左边的元素都不大于15，右边的元素都不小于15

切分操作的实现代码：

private static int partition(int[] a, int lo, int hi){
    		int i=lo, j=hi+1;
    		int v=a[lo];
    		while (true){
    			while (a[++i]<v) 
    				if (i==hi)
    					break;
    			while (a[--j]>v)
    				if (j==lo)
    					break;
    			if (i>=j)
    				break;
    			swap(a, i, j);
    		}
    		swap(a, lo, j);
    		return j;
    	}

递归切分排序：

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 void sort(int[] a){
    		sort(a, 0, a.length-1);
    	}

切分轨迹：

lo=0, hi=9, i=5, j=4, v=15
    -6 7 6 -20 15 24 18 29 53 47 
    
    lo=0, hi=3, i=2, j=1, v=-6
    -20 -6 6 7 15 24 18 29 53 47 
    
    lo=2, hi=3, i=3, j=2, v=6
    -20 -6 6 7 15 24 18 29 53 47 
    
    lo=5, hi=9, i=7, j=6, v=24
    -20 -6 6 7 15 18 24 29 53 47 
    
    lo=7, hi=9, i=8, j=7, v=29
    -20 -6 6 7 15 18 24 29 53 47 
    
    lo=8, hi=9, i=9, j=9, v=53
    -20 -6 6 7 15 18 24 29 47 53

给出两个结论：

1.长度为N的无重复数组排序，快排平均需要~2NlnN次比较。

2.快排最多需要约(N^2)/2次比较，随机打乱数组能够预防这种情况。