快速排序算法

雙端掃描交換法:

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

    1. 以上幾種算法實現(xiàn)均可以保證遞進條件(即每次遞歸至少使得要處理的數(shù)據(jù)規(guī)模減少1歧匈,一般為軸)垒酬,該實現(xiàn)可能會出現(xiàn)遞進失敗的情形
    1. 遞進失敗情形的處理:
      出現(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);
    }
  }
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市呵燕,隨后出現(xiàn)的幾起案子棠绘,更是在濱河造成了極大的恐慌,老刑警劉巖虏等,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件弄唧,死亡現(xiàn)場離奇詭異,居然都是意外死亡霍衫,警方通過查閱死者的電腦和手機候引,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來敦跌,“玉大人澄干,你說我怎么就攤上這事∧” “怎么了麸俘?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長惧笛。 經(jīng)常有香客問我从媚,道長,這世上最難降的妖魔是什么患整? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任拜效,我火速辦了婚禮喷众,結果婚禮上,老公的妹妹穿的比我還像新娘紧憾。我一直安慰自己到千,他們只是感情好,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布赴穗。 她就那樣靜靜地躺著憔四,像睡著了一般。 火紅的嫁衣襯著肌膚如雪般眉。 梳的紋絲不亂的頭發(fā)上了赵,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機與錄音煤篙,去河邊找鬼斟览。 笑死,一個胖子當著我的面吹牛辑奈,可吹牛的內(nèi)容都是我干的苛茂。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼鸠窗,長吁一口氣:“原來是場噩夢啊……” “哼妓羊!你這毒婦竟也來了?” 一聲冷哼從身側響起稍计,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤躁绸,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后臣嚣,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體净刮,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年硅则,在試婚紗的時候發(fā)現(xiàn)自己被綠了淹父。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡怎虫,死狀恐怖暑认,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情大审,我是刑警寧澤蘸际,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站徒扶,受9級特大地震影響粮彤,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一驾诈、第九天 我趴在偏房一處隱蔽的房頂上張望缠诅。 院中可真熱鬧,春花似錦乍迄、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至谅将,卻和暖如春漾狼,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背饥臂。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工逊躁, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人隅熙。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓稽煤,卻偏偏與公主長得像,于是被迫代替她去往敵國和親囚戚。 傳聞我的和親對象是個殘疾皇子酵熙,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容