排序算法（二）快速排序

快速排序

原理

之是以說快速排序是特殊的冒泡排序，其實質就是二分後再進行冒泡排序，這樣就可以節約時間了。

在二分後，即将待排序數組分成兩部分後，進行排序這個過程可以遞歸進行。

其實這裡快速排序總讓我想起小時候的拼圖玩具，先把一塊拼圖移到邊角，然後裡面開始拼，中間可能會交換移到邊角位的碎片，快速排序的參照位就相當于拼圖邊角位，先不管它，把大于它的都扔到右邊，小的扔左邊，然後把最後交點位置的前一位(交點位置的數字未比較大小)也就是比他小的數字交換到邊角位。

時間複雜度

示例代碼

整數排序示例

public static void sort(int[] data){
    sort(data,0,data.length-1);
}
	
public static void sort(int[] data, int start, int end){
    if(start>end){
	return;
    }
    int i=start,j=end;
    int key = data[start];
    while(i!=j){
	//按j--方向周遊目标數組，直到比key小的值為止
	while(i<j&&data[j]>=key){
	    j--;
	}
        //按i++方向周遊目标數組，直到比key大的值為止
        //此處一定要小于等于零，假設數組之内有一億個1，0交替出現的話，而key的值又恰巧是1的話，那麼這個小于等于的作用就會使下面的if語句少執行一億次
        while(i<j&&data[i]<=key){
	    i++;
	}
        if(i<j){
	    int temp = data[i];
	    data[i]=data[j];
	    data[j] = temp;
	}
    }
    //此時i==j
    data[start]=data[i];
    data[i]=key;
    //遞歸調用，把key前面的完成排序
    sort(data, start, i-1);
    //遞歸調用，把key後面的完成排序
    sort(data, j+1, end);
}                

優化或拓展

快速排序本身是先定下參照數，再根據參照數進行切割數組進行遞歸。那麼優化可以從參照數确立，切割數組，遞歸這三個方面入手。

先從參照數确立開始，那麼我們确立的參照數越靠近中間數（最後排序完成後最中間位置的值），那麼切割的次數越少。

三平均分區：取三個數（第一個、中間那個、最後一個），然後讓值在中間的那個做參照。

public static int sortByThree(int[] data, int start, int end){
		if(start>=end){
			return 0;
		}
		int index = 0;
		int i=start,j=end,mid=(end+start)/2;
		mid = data[start]-data[mid]<0?
				data[mid]-data[end]<0?mid:data[start]-data[end]<0?end:start:
				data[end]-data[mid]<0?mid:data[start]-data[end]<0?end:start;
		int key=data[mid];
		ArrayUtil.swap(data,start,mid);
		while(true){
			//這裡做了微調，首先去除i<j,這個條件已在後面做了判斷，每次循環減少一個判斷條件，這裡的i,j相當于指針的概念，i向右移動，j向左移動
			//用減法小于0更有趨于compareTo條件的寫法
			//并滿足條件進行break,更有利于代碼的了解
			while(data[++i]-key<0){
				if(i==end) break;
			}
			while(data[j]-key>0){
				j--;
				if(j==start) break;
			}
			if(i>=j) break;
			ArrayUtil.swap(data,i,j);
			index++;
		}
		//此時i,j相遇，交換參照數和相遇點的值
		ArrayUtil.swap(data,start,j);
		index++;
		//遞歸調用，把key前面的完成排序
		sortByThree(data, start, j-1);
		//遞歸調用，把key後面的完成排序
		sortByThree(data, j+1, end);
		return index;
	}                

測試當數組大于1000後效果還是比較明顯的。

也有說那個不如随機取，根據機率論我們擷取到中間值的幾率會随着次數增多而變大，那麼我們就來進行随機取值看看（也就是替換三平均分區的mid為随機值）。

測試結果比較

随機生成一組值區間為-10000~10000，長度15000的數組進行快速排序，三種方法耗時比較結果

just simple sort cost time -->9420ms
just three sort cost time  -->5460ms
just random sort cost time -->1909ms

just simple sort cost time -->14588ms
just three sort cost time  -->7167ms
just random sort cost time -->2436ms

just simple sort cost time -->14309ms
just three sort cost time  -->7325ms
just random sort cost time -->1870ms                

以上結果表明确實随機取參照效率來的高。

再從遞歸入手，最後資料量小的時候遞歸性能開銷較大，這裡可以考慮使用插入排序來替換一定長度（示例中為100，具體數字需要論證）的數組的排序。

public static void sortComplexInsert(int[] data, int start, int end){
		if(end-start<=0) return;
		else if(end-start<=100){
			for(int i=start+1;i<end-start+1;i++){
				int key = data[i];
				int j=i-1;
				while(j>=0&&data[j]>key){
					data[j+1]=data[j];
					j--;
				}
				data[j+1]=key;
			}
			return;
		}
		int i=start,j=end;
		while(true){
			while(data[++i]-data[start]<0){
				if(i==end) break;
			}
			while(data[j]-data[start]>0){
				j--;
				if(j==start) break;
			}
			if(i>=j) break;
			ArrayUtil.swap(data,i,j);
		}
		ArrayUtil.swap(data,start,j);
		sortComplexInsert(data,start,j-1);
		sortComplexInsert(data,j+1,end);
	}                

同樣以15000長度的數組測試，結果如下

just simple sort cost time  -->28054ms
quick insert sort cost time -->8943ms

just simple sort cost time  -->27395ms
quick insert sort cost time -->8616ms

just simple sort cost time  -->7566ms
quick insert sort cost time -->10388ms                

多次測試後，得出結論，效率高低和待排序數組的結構有很大的關系，同意可能出現普通快排效率高的可能，但是機率較低，是以對于未知的大的數組排序還是推薦在長度短的時候進行插入排序。

再從分割入手，既然分成了幾個部分，那麼我們就可以考慮多線程來處理。當然考慮到線程的建立是個耗時的操作，是以我們需要設定一個分區數峰值來開啟線程和結束線程。這邊主要是考慮實作，是以具體值不做論證。（測試功力太差）

适用環境

适用于數量較大并且記憶體足夠的情況。

版權聲明：本文為CSDN部落客「weixin_34106122」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：https://blog.csdn.net/weixin_34106122/article/details/92046508