歸并排序算法可以通過以下步驟實現:
mergeSort
,接收一個整數數組 arr
,以及數組的開始索引 start
和結束索引 end
。start
小于 end
,則計算數組的中間索引 mid
,并遞歸調用 mergeSort
函數,將數組分為兩個子數組進行排序:mergeSort(arr, start, mid)
和 mergeSort(arr, mid+1, end)
。merge
,接收三個整數數組 arr
、start
、mid
和 end
。該函數用于合并兩個已排序的子數組。首先創建兩個臨時數組 leftArr
和 rightArr
,分別用來存儲左子數組和右子數組的元素。arr
的元素從 start
到 mid
復制到 leftArr
中,將元素從 mid+1
到 end
復制到 rightArr
中。i
、j
和 k
,分別表示 leftArr
、rightArr
和 arr
的當前元素索引。leftArr[i]
和 rightArr[j]
的大小,將較小的元素復制到 arr[k]
,并將對應的索引遞增。重復這一步驟,直到 leftArr
或 rightArr
的元素全部被復制到 arr
中。leftArr
或 rightArr
復制到 arr
的剩余位置。mergeSort(arr, 0, len(arr)-1)
來對整個數組進行排序。以下是完整的 C 語言代碼實現:
#include <stdio.h>
void merge(int arr[], int start, int mid, int end) {
int i, j, k;
int n1 = mid - start + 1;
int n2 = end - mid;
int leftArr[n1], rightArr[n2]; // 臨時數組
// 將原始數組的元素復制到左右子數組中
for (i = 0; i < n1; i++)
leftArr[i] = arr[start + i];
for (j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
// 合并左右子數組到原始數組
i = 0;
j = 0;
k = start;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// 將剩余的元素從左右子數組復制到原始數組
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
void mergeSort(int arr[], int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
運行以上代碼,輸出結果為:
Sorted array:
3 9 10 27 38 43 82