快速排序簡單實踐

今天來用Java簡單實作一個快速排序，首先，針對快速排序裡最重要的一個知識：為什麼哨兵位置與初始掃描位置一定要分居左右兩側？，我們給出形象化的說明

首先，我們正向推導，也就是當哨兵位置為數組最左側start，兩個掃描指針分别是left和right，為什麼從right開始可行？

一次快排遞歸的while循環的退出條件是 l e f t = = r i g h t left == right left==right，如果優先進行 n u m s r i g h t > = n u m s s t a r t nums_{right}>=nums_{start} numsright​>=numsstart​的判斷，在達成退出條件時，退出位置一定僅包含以下兩種情形：

• 由 r i g h t right right向左掃描至 l e f t = = r i g h t left == right left==right，由于未移動的 n u m s l e f t nums_{left} numsleft​一定滿足 n u m s l e f t < = n u m s s t a r t nums_{left}<=nums_{start} numsleft​<=numsstart​，是以我們可斷言此時終止位置一定小于等于哨兵位置
• 由 l e f t left left向右掃描至 l e f t = = r i g h t left == right left==right，此時由于 r i g h t right right優先掃描，是以 n u m s r i g h t nums_{right} numsright​的狀态一定滿足 n u m s r i g h t < n u m s s t a r t nums_{right}<nums_{start} numsright​<numsstart​，我們可斷言此時終止位置一定小于哨兵位置

是以，從正向推導的角度，我們可說明哨兵位置與初始掃描位置分居兩側可保證終止位置小于等于哨兵位置。

為證必要性，也可反向推導當位于同一側時，是無法保證終止位置小于等于哨兵位置的，進而也就無法交換兩者

我們給出一個快排的Java實作例：

public void fastSort(int[] nums, int start, int end){//左閉右閉
    if(start >= end) return;
    int flag = nums[start];
    int left = start;
    int right = end;
    while(left < right){
        while(nums[right] >= flag && left < right) {
            right--;
        }
        while(nums[left] <= flag && left < right){
            left++;
        }
        if(left < right){
            int[] tmp = nums[right];
            nums[right] = nums[left];
            nums[left] = tmp;
        }
    }
    int[] tmp = nums[start];
    nums[start] = nums[left];
    nums[left] = tmp;
    fastSort(nums, start, left - 1);
    fastSort(nums, left + 1, end);
}
           

對于二維數組的快排，其原理和上述是一緻的，但仍然有一個更好的方法去簡單的實踐它，即調用Arrays.sort()接口方法，下面給出一種對二維數組進行升序排列**（自定義比較次元）**的寫法（假定二維數組的第二維大小為2，首先比較int[0]，相等時比較int[1]）

//int[][] points;
Arrays.sort(points, new Comparator<int[]>(){
	 @Override //可不帶Override，帶上更為标準
     public int compare(int[]o1, int[] o2){
         if(o1[0] == o2[0]) return o1[1] - o2[1];
         else return o1[0] - o2[0];
     }
});
           

compare函數的傳回值分為以下五類：

return 0:不交換位置，不排序

return 1:交換位置

return -1:不交換位置

return o1-o2:升序排列

return o2-o1:降序排列

PS1: 在使用(1,-1)這一類傳回值進行排序時，如果未聲明相等時傳回0，則會因為比較器無法逆向執行而形成

Comparison method violates its general contract

異常

PS2：在使用o1-o2/o2-o1這一類傳回值進行排序時，無需特殊聲明大小關系，但可能出現因超出int類型範圍而産生的值計算錯誤，進而影響排序結果

這裡再分享一個總結較為全面的部落格：Java中實作自定義排序的多種寫法