雙端掃描交換法：

i,j分別向前后掃描，遇到逆序隊(duì)則交換

• 循環(huán)退出條件：i<=j
  在內(nèi)部循環(huán)時(shí)始終要檢查該條件是否成立,因?yàn)閕，j一直在更新
• 循環(huán)退出后，i所在位置就是軸應(yīng)在位置

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 兩個(gè)部分
    while (i <= j) {
      while (i <= j && array[i] <= pivot) {
        i++;       // i 最終停在一個(gè) > pivot  的地方
      }
      while (i <= j && array[j] > pivot) {
        j--;      // j 最終停在一個(gè) <= high 的地方
      }
      if (i <= j) {       // 因?yàn)橹滥嫘驅(qū)ν顺?        swap(array, i, j);
      }
    }
    // 此時(shí)劃分完畢，且 i處于>pivot區(qū)首位置, j處于<=pivot區(qū)尾位置
    swap(array, low, j);               // i 指向劃分點(diǎn)
    sort_swap(array, low, j - 1);
    sort_swap(array, j + 1, high);
  }

雙端掃描填空法：

i,j分別向前后掃描，將空位數(shù)據(jù)保存在pivot中，一端始終持有空位，另一端掃描數(shù)據(jù)填入空位，交替操作

• 循環(huán)退出條件： i<j
  當(dāng)i==j時(shí)，交換完成，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

• 當(dāng)遇到array[j] > pivot時(shí),只更換位置，不更新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

• 當(dāng)遇到array[j] > pivot時(shí),向前查找到首個(gè)<=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 {
        // 找到第一個(gè)<=pivot的數(shù)，找不到(處理完畢)則會(huì)退出外循環(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

• 1. 以上幾種算法實(shí)現(xiàn)均可以保證遞進(jìn)條件(即每次遞歸至少使得要處理的數(shù)據(jù)規(guī)模減少1，一般為軸)，該實(shí)現(xiàn)可能會(huì)出現(xiàn)遞進(jìn)失敗的情形
• 2. 遞進(jìn)失敗情形的處理：
     出現(xiàn)條件：當(dāng)只能劃出一個(gè)分區(qū)時(shí)，則遞進(jìn)失?。挥伤惴ǖ妮S可以知道，算法一定會(huì)劃分出中間分區(qū)；
     即 遞進(jìn)失敗出現(xiàn)在只能劃分出中間分區(qū)時(shí)，此時(shí)必然有(i = low && j = high + 1)，而當(dāng)(i = low && j = high +
     1)時(shí)，必然只有一個(gè)中間分區(qū)，必然導(dǎo)致遞進(jìn)失敗;
     (i = low && j = high + 1) <==> 遞進(jìn)失敗
     處理方式：若劃分完成，(i = low && j = high + 1)條件成立，則必然low為最小值，而high為最大值,則對(duì)(i+1, j-2)或(low + 1, high - 1)進(jìn)行遞進(jìn)

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);
    }
  }