雙端掃描交換法：
i,j分別向前后掃描赌朋，遇到逆序隊則交換
- 循環(huán)退出條件：i<=j
在內(nèi)部循環(huán)時始終要檢查該條件是否成立,因為i珍手，j一直在更新 - 循環(huán)退出后裸扶，i所在位置就是軸應在位置
public static void sort_swap(int[] array, int low, int high) {
if (low >= high) {
return;
}
int pivot = array[low];
int i = low + 1, j = high;
// 被劃分為 >pivot 和 <= pivot 兩個部分
while (i <= j) {
while (i <= j && array[i] <= pivot) {
i++; // i 最終停在一個 > pivot 的地方
}
while (i <= j && array[j] > pivot) {
j--; // j 最終停在一個 <= high 的地方
}
if (i <= j) { // 因為知道逆序對退出
swap(array, i, j);
}
}
// 此時劃分完畢，且 i處于>pivot區(qū)首位置, j處于<=pivot區(qū)尾位置
swap(array, low, j); // i 指向劃分點
sort_swap(array, low, j - 1);
sort_swap(array, j + 1, high);
}
雙端掃描填空法：
i,j分別向前后掃描镣隶，將空位數(shù)據(jù)保存在pivot中漫试，一端始終持有空位，另一端掃描數(shù)據(jù)填入空位碘赖，交替操作
- 循環(huán)退出條件： i<j
當i==j時驾荣，交換完成外构，array[i]即為空位，填入pivot
public static void sort_fill(int[] array, int low, int high) {
if (low >= high) {
return;
}
int pivot = array[low];
int i = low, j = high;
// 劃分為<=pivot 和 >pivot 兩部分
while (i < j) { // i,j交替指向空位
while (i < j && array[j] > pivot) {
j--;
}
array[i] = array[j];
while (i < j && array[i] <= pivot) {
i++;
}
array[j] = array[i];
}
// i==j,且為空位
array[i] = pivot;
sort_fill(array, low, i - 1);
sort_fill(array, i + 1, high);
}
單向掃描三分法：
[low,i) <pivot; [i,j) =pivot; [j,k] 未掃描; (k,high] >pivot
- 當遇到array[j] > pivot時,只更換位置播掷，不更新j（換回來的array[k]也可能大于）
public static void sort_single_3(int[] array, int low, int high) {
if (low >= high) {
return;
}
int pivot = array[low];
int i = low, j = low + 1, k = high;
while (j <= k) {
if (array[j] == pivot) {
j++;
} else if (array[j] < pivot) {
swap(array, i, j);
i++;
j++;
} else {
swap(array, j, k);
k--;
}
}
sort_single_3(array, low, i - 1);
sort_single_3(array, k + 1, high);
}
雙向掃描三分法:
類似單向掃描三分法,[low + 1,i) <pivot; [i,j) =pivot; [j,k] 未掃描; (k,high] >pivot
- 當遇到array[j] > pivot時,向前查找到首個<=pivot的元素审编，根據(jù)是<pivot或是=pivot分別處理,注意始終檢查 j<= k是否成立
public static void sort_double_3(int[] array, int low, int high) {
if (low >= high) {
return;
}
int pivot = array[low];
int i = low, j = low + 1, k = high;
while (j <= k) {
if (array[j] == pivot) {
j++;
} else if (array[j] < pivot) {
swap(array, i, j);
i++;
j++;
} else {
// 找到第一個<=pivot的數(shù)，找不到(處理完畢)則會退出外循環(huán)
while (j <= k && array[k] > pivot) {
k--;
}
if (array[k] == pivot) { // 相等
swap(array, k, j);
j++;
k--;
} else { // 小于
swap(array, i, k);
swap(array, j, k);
i++;
j++;
k--;
}
}
}
sort_double_3(array, low, i - 1);
sort_double_3(array, k + 1, high);
}
雙軸雙向三分法:
pivot1 < pivot2,[low,i) <pivot1; [i,j) pivot1 <= x <= pivot2; [j,k] 未掃描; (k,high] >pivot2
- 以上幾種算法實現(xiàn)均可以保證遞進條件(即每次遞歸至少使得要處理的數(shù)據(jù)規(guī)模減少1歧匈，一般為軸)垒酬，該實現(xiàn)可能會出現(xiàn)遞進失敗的情形
- 遞進失敗情形的處理：
出現(xiàn)條件：當只能劃出一個分區(qū)時，則遞進失敿勘究；由算法的軸可以知道，算法一定會劃分出中間分區(qū)斟冕；
即 遞進失敗出現(xiàn)在只能劃分出中間分區(qū)時口糕，此時必然有(i = low && j = high + 1)，而當(i = low && j = high +
1)時磕蛇，必然只有一個中間分區(qū)景描，必然導致遞進失敗;
(i = low && j = high + 1) <==> 遞進失敗
處理方式：若劃分完成，(i = low && j = high + 1)條件成立秀撇，則必然low為最小值超棺，而high為最大值,則對(i+1, j-2)或(low + 1, high - 1)進行遞進
- 遞進失敗情形的處理：
public static void sort_dual_pivot_3(int[] array, int low, int high) {
if (low >= high) {
return;
}
if (array[low] > array[high]) {
swap(array, low, high);
}
int pivot1 = array[low], pivot2 = array[high];
int i = low, j = low + 1, k = high;
while (j <= k) {
if (array[j] < pivot1) {
swap(array, i, j);
j++;
i++;
} else if (pivot1 <= array[j] && array[j] <= pivot2) {
j++;
} else {
while (j <= k && array[k] > pivot2) {
k--;
}
if (array[j] < pivot1) {
swap(array, i, k);
swap(array, j, k);
i++;
k--;
j++;
} else {
swap(array, j, k);
j++;
k--;
}
}
}
if (low == i && j == high + 1) {
sort_dual_pivot_3(array, i + 1, j - 2);
} else {
sort_dual_pivot_3(array, low, i - 1);
sort_dual_pivot_3(array, i, j - 1);
sort_dual_pivot_3(array, k + 1, high);
}
}
