挖坑版是在Hoare版的基礎上做了改造，答題思路還是和Hoare版一樣，
挖坑版partition單次程序：
- 選一個基準值，一般選最左或者最右面，把該基準值存在val變數中，因為值存到了變數里，所以可以視為這個位置能放其他值了，
- 定義一個left和一個right參考，left從序列左向右走，right相反（如果基準值在左邊則right先走，如果基準值在右邊，left先走）
- 走的程序中，如果right遇到小于val的數，則把個數放在坑中，并在次形成坑位，然后left向右走，如果遇到大于val的數，則將值填入坑中，此處形成一個坑位，回圈下去，直到left和right相遇，這個時候把val的值放到坑中，
下面是單次partition動圖演示（圖是借的哈哈）
經過單次partition，讓val左邊的資料全部小于val，右邊的資料全部大于val，
然后在去處理val左邊子序列和val右邊子序列，思路在Hoare版里面已經講了，這里就不再重復了，
public static void quickSort(int[] array){
//把基準值選在待排序序列的最左邊，第一次就是 0 的位置，
quickSortRange(array, 0, array.length - 1);
}
private static void quickSortRange(int[] array, int from, int to) {
int size = to - from + 1;
//遞回結束條件
if (size <= 1)
return;
//先處理傳入序列，回傳值為一次單趟排序之后的基準值的位置，
//基準值左邊為左子序列，基準值右邊為右子序列
int index = partition(array, from, to);
//處理左子序列
quickSortRange(array, from, index - 1);
//處理右子序列
quickSortRange(array, index + 1, to);
}
public static int partition(int[] array, int from, int to) {
int left = from;
int right = to;
int val = array[left];
while (left < right) {
while (array[right] >= val && right > left)
right--;
array[left] = array[right];
while (array[left] <= val && right > left)
left++;
array[right] = array[left];
}
array[left] = val;
return left;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/297628.html
標籤：其他