goal00001111

     摘要: 插入排序是一種簡單的排序方法，因?yàn)榈膶?shí)現(xiàn)比較簡單，所以在數(shù)據(jù)量較少時應(yīng)用很廣泛。插入排序根據(jù)其插入的不同方式，可以分為直接插入排序，折半插入排序，2-路插入排序，表插入排序和希爾排序。在這里我將一一寫出各種插入排序的算法代碼。  閱讀全文

     摘要: 歸并排序算法以O(shè)（nlogn）最壞情形運(yùn)行時間運(yùn)行，而所使用的比較次數(shù)幾乎是最優(yōu)的。它可以用遞歸的形式實(shí)現(xiàn)，形式簡潔易懂。但是需要注意的是當(dāng)用遞歸形式時，如果數(shù)據(jù)較多，則開銷很大，實(shí)用性很差，所以我們一般采用非遞歸的形式。我這里兩種形式都給出。  閱讀全文

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

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