首先我先聲明，這不是學校作業，是我想更了解 qsort 的運用
基本上，bobble sort 是可以很容易理解他的運作方式
就是兩個數比較，而大的往上推
那 qsort 呢? 老實說我無法從他的程式碼來理解他的運作方式
可以解釋他是怎麼運作的嗎?
希望能詳細一點
2006-07-13 09:56:12 · 5 個解答 · 發問者 韋名 2 in 電腦與網際網路 ➔ 程式設計
qsort全名是Quich Sort，名稱來由是因為他在平常應用上是最快、最方便的一種排序方法。
他的方法就是在陣列中選一個數(假設是a)當作flag，把所有大於a的數字放到a的右邊，小於的就放左邊，再對左右兩邊的陣列(不包括a)進行遞迴，終止條件為陣列長度小於二。
他的優點有幾個：
1)他的時間複雜度"平均"是O(n lg n)，但如果對象是已經排序過的陣列，而且每次選取那個旗標的方法不好(像是每次都選最左邊的數)會造成複雜度變成O(n^2)，所以一般在實作時會使用隨機的方法，選取旗標時隨機選一個元素而不指定要用陣列開頭，用此方法避免掉worst case的發生
2)在執行函式內容(把數字分兩邊)時不需要額外的記憶體，只需要在排序的對象陣列中做元素的重排，不像merge sort或是heap sort需要另外宣告記憶體來實做
3)qort是一種stable的排序方法，所謂的stable是說當元素的關鍵值(排序依據)相同時，這些元素在函式完成十的排列順序必須和原本一樣。例如下面有個陣列:
a4 b1 c3 d5 e3
按照後面的數字作遞增排序，如果是stable sorting時結果是
b1 c3 e3 a4 d5 (注意其中c3和e3的排列順序)
但如果是unstable的sorting可能結果會變成
b1 e3 c3 a4 d5
至於達成這個特性的方法也很簡單，只要在函式內部把數字分邊時按照陣列原本的順序就可以(也就是說通常寫出來的都是stable的)
基於上面幾點，平常在做排序的時候通常都是用qsort，在C++的standard library裡面的
2006-07-14 21:22:50 補充：
和其他的O(n lg n)的排序方式比較起來，qsort的constant factor小很多
2006-07-14 17:20:29 · answer #1 · answered by YuFan 2 · 0⤊ 0⤋
大致上就是先選一個數
把這個數當做中間數
之後把這個陣列的數分成左右兩堆
就是所有比這個數小的丟到左邊
比這個數大的丟到右邊
在左右兩邊遞迴排下去之後
就是排好的陣列了
2006-07-13 12:14:30 · answer #2 · answered by ? 3 · 0⤊ 0⤋
課本有啊!
那是內部運算最快的三個方法之一!
而且,雖然同是 O(N log N)，但它較適合寫成電腦較短時的指令，所以，其它 O(N log N)快！
缺點：worst case 實在太差！
去找 Algorithm (演算法）的課本，一定有！
2006-08-02 19:20:58 補充：
Merge sort 〝可以〞不用額外的 RAM 喔!
我對 Merge Sort 不是很有興趣，沒啥研究。不過，我做過一題用 Merge Sort 但不可以用額外 RAM 的習題。成功！^_^ 只是不記得那是否是 Merge Sort 的特例了。
但，至少有一例可以，不是嗎？
2006-07-13 11:12:15 · answer #3 · answered by ? 7 · 0⤊ 0⤋
謝謝,但我只找得到程式碼,找不到說明
2006-07-13 15:46:06 補充：
sorry,我是高中生
2006-07-13 10:22:26 · answer #4 · answered by 韋名 2 · 0⤊ 0⤋
應該是從他運作的方式去寫程式碼吧
網路應該有他的運作方式
2006-07-13 10:21:05 · answer #5 · answered by 大 3 · 0⤊ 0⤋