goal00001111

     摘要: 快速排序是在實踐中最快的已知排序算法，它的平均運行時間是O（NlogN）。該算法之所以特別快，主要是由于非常精練和高度優化的內部循環。在隊列中尋找合適的樞點元素，并按樞點元素劃分序列，是快速排序算法的關鍵。
為簡單起見，我這里數組的第一個元素作為樞點元素，重新排列數組，使得樞點元素之前的元素都小于樞點元素，而樞點元素之后的元素都大于或等于樞點元素。  閱讀全文

     摘要: 排序在最壞的情況下，其時間復雜度也能達到O（nlogn）。相對于快速排序來說，這是它最大的優點，此外，堆排序僅需要一個記錄大小供交換用的輔助存儲空間。
堆排序的數據結構是二叉堆，二叉堆的特點有兩個，一個是它是一棵完全二叉樹，另一個是它的根結點小于孩子結點，所以我們很容易找到它的最小結點----根結點；當然如果你想找到最大結點的話，那就要掃描所有的葉子結點，這是很費時間的，如果你想找的是最大結點的話，你最好把它弄成一個大頂堆，即一棵根結點大于孩子結點的完全二叉樹。
二叉堆通常用數組來實現，它舍棄下標0，從下標1開始置數，則很容易滿足，對于數組中任意位置i上的元素，其左兒子的位置在2i上，右兒子的位置在2i+1上，雙親的位置則在i/2上。
堆排序的算法之一是把數組構建成二叉堆----這只要增添一個長度為n+1的輔助空間，然后把原數組的元素依次插入到二叉堆即可。然后刪除二叉堆的根，把它作為排序后的數組的第一個元素,然后使二叉堆的長度減1，并通過上移使得新得到的序列仍為二叉堆，再提取新二叉堆的第一個元素到新數組。依此類推，直到提取最后  閱讀全文