程序員能20分鐘徒手寫出一個沒bug的快速排序嗎？（可以調試）

能寫出來的同學請說明一下自己為什麼可以寫出來

http://jishu.zol.com.cn/2714.html

補充：在不使用高級語言的一些特性、函數的前提下，如 filter。以及不使用額外空間，必須 in place.

---

能，因為參加過 「全國青少年信息學奧林匹克競賽」

---

看了樓上各位我就不獻醜了，所以說題主你忘了一群人，叫做OIer/ACMer……我/他們的存在，就是這樣的。

---

可以

快排的關鍵在於分割

正確理解分割關鍵在於這個演算法的循環不變式

---

我們準備OI的時候都是關屏幕盲打快排直接運行，過不了的請客吃飯滴

---

地鐵上無聊手機用了十幾分鐘打的 =。= 有鍵盤的話能快不少。

沒法添加格式回去再改。

quicksort :: (Ord a) =&> [a] -&> [a]
quicksort [] = []
quicksort (x:xs) =
let smaller = quicksort [a | a &<- xs, a &<= x] bigger = quicksort [a | a &<- xs, a &> x]
in smaller ++ [x] ++ bigger


為什麼寫的出？因為印象很深。。

---

def qsort(numbers):
if len(numbers) == 0: return []
else: return qsort([i for i in numbers[1:] if i &<= numbers[0]]) + [numbers[0]] + qsort([i for i in numbers[1:] if i &> numbers[0]])


看到 Erlang 那個手癢寫一個Python... 為什麼能寫出來。。因為懂原理

---

看到題目後，回答的都是會的，不會的當作沒看見。

---

quicksort=: (($:@(&<#[), (=#[), $:@(&>#[)) ({~ ?@#)) ^: (1&<#)

---

不用鍵盤估計不行。

得看語言，大部分語言是可以的。

---

來個python版，分分鐘搞定

def qsort(arr):
if len(arr) &<= 1: return arr return qsort([x for x in arr if x &< arr[0]]) + [x for x in arr if x == arr[0]] + qsort([x for x in arr if x &> arr[0]])


---

fun qsort [] =&> []; qsort (x!xs) =&> qsort (filter .{ #a &< x; } xs) @ [x] @ qsort (filter .{ #a &>= x; } xs); end;


---

我覺得兩類人都能寫出來

1. 學了快排而且不是只學過快排，有基本編程能力的，沒理由寫不出來：先不考慮就地排序，做個partition，然後遞歸幾分鐘能寫完吧。如果說隨便選一個標準，然後掃一遍整個序列看個大小分個組都能寫不出，沒理由算具有基本編程能力吧。看著寫好的基本快排，把partition改成就地的也可以幾分鐘搞定。就算真的只學了快排和一些基本演算法，隨便寫個暴力的把檢查過的位置分成大小兩組的方法，也立刻能看出怎麼寫可以保證線性時間完成劃分吧。總時間一共20min，還有幾分鐘可以看看有沒有一時大意寫錯的細節。（寫不完的是學了快排還是只看了一眼快排的描述我很懷疑）
2. 背過：這個不用解釋了。學競賽的出於應試目的多數要背一下避免浪費時間，反正學競賽的大部分也不缺這個時間。

說來慚愧，我一開始存粹是因為第二種原因，後來才自己學的。當初OI時期腦洞太大，寫快排必隨機三數中值劃分+折半遞歸+底層插入排序優化（用堆優化太sxbk了干不出來），實際上好像對競賽什麼效果也沒有。

20min寫快排好像沒什麼意義，但是學過快排學過編程的20min寫不出大概有問題。快排又不是什麼不搞個競賽就幾乎不可能會的東西。

———————————————————————————————————————————

不對我要修改一下，如果你用BrainF**k, Whitespace之類的，那可能基本編程技能20min是不夠……

---

我記得有次我用不到十分鐘在gedit里寫完了。沒打草稿，一次編譯通過(這是一定的了)，然後邏輯有點錯誤導致跳出循環後的pivot值沒有swap。。又改了一次，完美執行！

---

當然可以啊~

看過Jon Bently那個快排，一輩子都忘不了了，背下來就可以了。

void quicksort(int l, int u){
int i, m;
if(l &>= u) return;
m = l;
for(i = l+1; i&<= u; i++) if(x[i] &< x[l]) // buggy! swap(++m, i); swap(l, m); quicksort(l, m-1); quicksort(m+1, u); }

上面是他在 beautiful code 上的代碼。

最核心的部分就是開始的那個for循環和swap了（paritition），這要怎麼背呢？當然是用循環不變式了！

[l+1, m] 位置保存著當前已處理元素之中所有的小於pivot的元素

i指向的是下一個待處理的元素

第l個元素是pivot

循環開始時，[l+1, m]是空集，已處理元素也是空的，所以循環不變式成立。

for循環每輪把i加了1，這樣就有可能破壞循環不變式，

怎麼辦呢，當然是：

在i加1之前，如果發現當前i指向的值小等於pivot，就將m自增1，並且和i指向的元素交換。

這樣，循環不變式又成立啦。

在for循環結束後，循環不變式依然是成立的（根據數學歸納法~）

那麼，它告訴了我們什麼性質呢？

[l+1, m]之間包含了l 到 u 之間的小於 pivot 的元素，且第l個元素是pivot。

於是，我們只要將第l個元素和第m個元素交換，就完成了partition的操作，即：pivot在第m個元素上，m元素之前的值都小於pivot，之後的值都大等於pivot。

非常簡潔，非常酷炫，但是有點bug（注意我注釋的那一行）

這個partition在大量duplicate key的情況下，會把這些key全部放到左邊或者右邊。導致不公平的切分。

partition要保證在中間把數組分開，可以看這個代碼：

代碼中，數組不是被切成兩份，而是三份，中間那份包含了所有和pivot相同的key。

左邊和右邊那份分別是比pivot小和比pivot大的key，遞歸調用僅在它們之上執行，中間那份在partition後就保留在原地不動了。

public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
assert isSorted(a);
}

// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
if (hi &<= lo) return; int lt = lo, gt = hi; Comparable v = a[lo]; int i = lo; while (i &<= gt) { int cmp = a[i].compareTo(v); if (cmp &< 0) exch(a, lt++, i++); else if (cmp &> 0) exch(a, i, gt--);
else i++;
}

// a[lo..lt-1] &< v = a[lt..gt] &< a[gt+1..hi]. sort(a, lo, lt-1); sort(a, gt+1, hi); assert isSorted(a, lo, hi); }

參考：

Quicksort

---

快排演算法我們小學編程競賽隊人人都背過。不僅如此，我們還能在紙上用腦子 Debug 和運行程序呢。

---

void qsort(int arr[],int l,int r)
{
int i=l,j=r,k=arr[(l+r)&>&>1];
while (i&k)j--;
if (i&<=j) { swap(arr[i],arr[j]); i++; j--; } } if (l&

好久不手寫快排了,這個貌似還是初中的版本.

---

.......

---

這是我去面試微軟實習生的時候，其中一道面試題，我花了10分鐘用C語言寫了出來。至於說為什麼能嘛，快速排序又不複雜。

後面還有人讓我徒手把一個循環寫成指令什麼的。

---

qsort = lambda l: l if len(l) &<= 1 else qsort([i for i in l[1:] if i&<= l[0]]) + l[:1] + qsort([i for i in l[1:] if i&>l[0]])


逗比Python版，一點用沒有，效率挫的一比.

匿了.

---

應該加一條，不許用遞歸。

---

推薦閱讀：