首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> 更多程式語言 >> 程式設計綜合問答

快速排序單趟划分:基準值選擇與交換策略導致的結果不確定性

     編輯:程式設計綜合問答

題目

序列 (5, 2, 6, 3, 8),以首元素 5 為基準進行一趟快速排序,四個選項結果各異。

核心結論

標準快排划分算法(Hoare/Lomuto)的具體交換細節決定最終序列,題目未限定算法細節,故 ABC 皆可能正確。

三種常見划分結果演示

算法變體關鍵步驟一趟後序列對應選項
Lomuto(教科書常見)i/j 雙指針,最終將基準交換到 j 位置3, 2, 5, 6, 8C
Hoare(原版)左右掃描交換,基準不動,最終返回分界點3, 2, 5, 8, 6B
雙向掃描+基準先放末尾基準 5 換到末尾,划分後再換回2, 3, 5, 8, 6A

面試/考試應對

  1. 若題目給出具體偽代碼,嚴格按偽代碼跑。
  2. 未給代碼時,說明「取決于划分算法實現」,並寫出最常見的 Lomuto 結果(選項 C)為首選答案。
  3. 補充:「工程實踐中常用三數取中法選基準 + 隨機化划分,避免最壞情況。」
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved