溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
上一篇文章寫了一個自頂向下的歸并排序，把一個完整的數組不斷二分，然后再合并。其實換一種思路：把數組中相鄰的N個元素看成是已經二分好了的，直接進行合并，就省掉了二分那一步驟
自底向上的歸并排序示意圖
C++實現:
template<typename T>
void mergeSortButton2Top(T arr[], int n) {
for (int size = 1; size <= n; size += size) {
for (int i = 0; i+size < n; i+=2*size) //對[i,i+size-1]和[i+size,i+2*size-1]進行歸并
__merge(arr, i, i + size - 1, min(i + size + size - 1,n-1));// arr left mid right 如果i+2*size>n了，越界了，就取n-1
}
}
template<typename T>
void __merge(T arr[], int left, int mid, int right) { //將arr[left,mid] 和 arr[mid+1,right] 兩部分進行歸并
T *tmp=new T[right-left+1];
for (int i = left; i <= right; i++)
tmp[i - left] = arr[i]; //先把arr（需要合并的左右片段） 復制給tmp
int i = left, j = mid + 1; // i 做為左半部分的指針 j作為右半部分的指針
for (int k = left; k <= right; k++) {
if (i > mid) { // 左半部分 已經合入完了，將右半部分剩下的 全部合入
arr[k] = tmp[j - left];
j++;
}
else if (j > right) { // 右半部分 已經合入完了，將左半部分剩下的 全部合入
arr[k] = tmp[i - left];
i++;
}
else if (tmp[i - left] < tmp[j - left]) {
arr[k] = tmp[i - left];
i++;
}
else {
arr[k] = tmp[j - left];
j++;
}
}
delete[] tmp;
}
int main() {
int arr[9] = { 1,5,6,78,12,5,1,12,54 };
mergeSortButton2Top(arr,9);
for (int i = 0; i < 9; i++) {
cout << arr[i]<<" ";
}
return 0;
}
GoLang實現:
func mergeSortButton2Top(arr [] int) {
var lenth int = len(arr)
for size := 1; size <= lenth; size += size {
for i := 0; i+size < lenth; i += 2 * size { //對[i,i+size-1]和[i+size,i+2*size-1]進行歸并
merge(arr, i, i+size-1, int(math.Min(float64(i+2*size-1), float64(lenth-1))))// arr left mid right 如果i+2*size>n了，越界了，就取n-1
}
}
}
func merge(arr []int, left, mid, right int) {
// 將要合并的部分做個拷貝
var tmp []int = make([]int, right-left+1)
for i, j := left, 0; i <= right; i++ {
tmp[j] = arr[i]
j++
}
// i做為左半部分的指針 j作為右半部分的指針
var i, j int = left, mid+1
for k := left; k <= right; k++ {
if i > mid { // 左半部分 已經合入完了，將右半部分剩下的 全部合入
arr[k] = tmp[j-left]
j++
} else if j > right { // 右半部分 已經合入完了，將左半部分剩下的 全部合入
arr[k] = tmp[i-left]
i++
} else if tmp[i-left] > tmp[j-left] {
arr[k] = tmp[j-left]
j++
} else {
arr[k] = tmp[i-left]
i++
}
}
}
用golang對兩種歸并排序進行計時，觀察性能：
func createRandomArray(count int) []int {
rand.Seed(time.Now().UnixNano())
var arr [] int = make([]int, 0)
for i := 0; i < count; i++ {
arr = append(arr, rand.Intn(100))
}
return arr
}
func main() {
count := 10000
arr := createRandomArray(count)
var arr2 []int = make([]int, count)
copy(arr2, arr)
start := time.Now()
mergeSort(arr, 0, len(arr)-1)
fmt.Println("自頂向下歸并排序 用時：", time.Since(start))
start = time.Now()
mergeSortButton2Top(arr2)
fmt.Println("自底向上歸并排序 用時：", time.Since(start))
}
//輸出：
//自頂向下歸并排序 用時： 4.997ms
//自底向上歸并排序 用時： 3.9987ms
因為自底向上少了二分那個步驟，性能要優于自頂向下的歸并排序
總結
到此這篇關于C++/GoLang如何實現自底向上的歸并排序的文章就介紹到這了,更多相關C++/GoLang自底向上的歸并排序內容請搜索億速云以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持億速云！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
