You work at the college library. You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make matters worse, classes start tomorrow, which means that first thing in the morning, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to start at one end of the line with the first pair of books. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the partition on its left and all the ones that come after it on its right. You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most efficient strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given location sorted by distance. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.
你是大學圖書館的管理員。 正在享受午後的閒暇時光。 這時候,突然送來了1280 本書! 這些書被排成一行, 但是毫無規律。 剛好,自動分類系統又發生故障。 更糟糕的是,明天就要開學了; 也就是說明天一大早, 學生們就會湧入圖書館借書。 如何才能把所有書籍 及時整理好? 第一種方法:你可以從 排在最前面的兩本書開始, 如果這兩本書的順序正確, 那麼不做任何變動; 否則,互相交換這兩本書的位置。 接著再看第二本書和第三本書, 不斷重複上述過程, 一直到書列的末端為止。 在過程中,你可能就會碰到 應該排在最後的那一本書, 你會持續將這本書和後面的書交換, 將它不斷往後移動, 一直到最後面的位置。 然後再從頭開始, 不斷重複上述的步驟, 將倒數第二本書歸位, 一直持續到所有的書 都放在正確的位置為止。 這種整理的方法 叫做「氣泡排序法」。 原理很簡單,但過程很緩慢。 在第一輪過程就需要進行 1279 次的比較; 第二輪要比較 1278 次, 以此類推…… 所以總共要比較 818,560 次。 如果比較一次需要 1 秒, 那麼你需要花費 9.5 天才能完成工作。 第二種方法是先將前面兩本書排好, 然後將第三本書 與位於第二位的書進行比較。 如果第三本書應該放在第二本之前, 則互相交換它們的位置, 然後再將這本書 與排在第一位的書比較, 如果有需要,就再交換位置。 現在,你已經成功安排好了前三本書, 接著每次將一本書 加入之前安排好的隊列中, 將新書與前一本作比較, 如果需要,交換它們的位置, 一直到這本新書被安置到 隊列中的正確位置。 這種方法叫做「插入排序法」。 與氣泡排序法不同, 它通常不需要比較 所有相鄰的兩本書。 平均來說,每本書 需要進行比較的次數 僅有氣泡排序法的一半。 這種方法總共需要比較 409,280 次, 大約需要 5 天時間。 然而,你需要比較的次數還是太多。 更好的辦法是, 首先,隨機選取一本書, 我們稱之為「分割點」; 將其他的每一本書 與分割點作比較, 然後根據分割點, 將這一排書分成兩部分, 將所有應該在分割點 之前的書放在左邊, 在分割點之後的書放在右邊, 這樣你就節省了大把時間, 因為不用再將分割點左半邊的書 與右邊的書進行比較。 現在,我們只關注分割點左邊的書, 你可以再一次隨機選一本書 作為新的分割點, 然後將其他的書分配在 新的分割點左右兩邊。 你可以繼續建立這種「子分割點,」 一直到分出了許多小型分支, 每一個分支中, 可以用其他更快的排序法, 例如插入排序法。 每一輪分割大約需要 進行 1280 次比較, 如果你的分割點分佈的非常均勻, 整排書分為 128 個分支, 每個分支 10 本書, 這樣大約需要七輪分割, 也就是 8960 秒。 每個分支當中, 大約需要再花 22 秒進行排序。 總體上來說, 這種稱為「快速排序法」的方法, 能將所有的書 在三個半小時內排列整齊。 但是這有個陷阱。 如果你的分割點非常偏向某一端, 就無法節省時間。 幸運的是,這種情況幾乎不會發生。 這就是為什麼快速分類法 在程式設計中 是最有效率的排序法之一。 例如在購物網站上, 將商品依照價格排序; 或是列出某個地點附近的加油站, 然後根據距離來排序。 在這個排書的例子中, 快速排序法幫你節省了許多時間。 真是多麼驚險刺激的一天啊!