摘要： 前面講了插入排序，交換排序，選擇排序，下面接著來講歸并排序。 歸并排序(Merge Sort)是利用"歸并"技術(shù)來進(jìn)行排序。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。 歸并排序 基本思想：設(shè)兩個(gè)有序的子序列(相當(dāng)于輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合并到一個(gè)局部的暫存序列 temp (相當(dāng)于輸出序列)中，待合并完成后將 temp 復(fù)制回 array[low..high]中，從而完成排序。 在具體的合并過程中，設(shè)置 i，j 和 p 三個(gè)指針，其初值分別指向這三個(gè)記錄區(qū)的起始位置。合并時(shí)依次比較 array[i] 和 array[j] 的關(guān)鍵字，取關(guān)鍵字較小（或較大）的記錄復(fù)制到 temp[p] 中，然后將被復(fù)制記錄的指針 i 或 j 加 1，以及指向復(fù)制位置的指針 p 加 1。重復(fù)這一過程直至兩個(gè)輸入的子序列有一個(gè)已全部復(fù)制完畢(不妨稱其為空)，此時(shí)將另一非空的子序列中剩余記錄依次復(fù)制到 array 中即可。 閱讀全文