48 lines
1.5 KiB
C
48 lines
1.5 KiB
C
#include <stdio.h>
|
|
// 归并函数
|
|
void merge(int arr[], int left, int middle,
|
|
int right, int temp[]) {
|
|
int i = left; // 左数组起始索引
|
|
int j = middle + 1; // 右数组起始索引
|
|
int k = left; // 合并后数组起始索引
|
|
// 将数据复制到临时数组
|
|
for (int m = left; m <= right; ++m)
|
|
temp[m] = arr[m];
|
|
// 合并临时数组到 arr[left..right]
|
|
while (i <= middle && j <= right) {
|
|
if (temp[i] <= temp[j])
|
|
arr[k++] = temp[i++];
|
|
else
|
|
arr[k++] = temp[j++];
|
|
}
|
|
// 拷贝剩余元素（如果有）
|
|
while (i <= middle)
|
|
arr[k++] = temp[i++];
|
|
}
|
|
// 归并排序函数
|
|
void mergeSort(int arr[], int left, int right, int temp[]) {
|
|
if (left < right) {
|
|
int middle = left + (right - left) / 2;
|
|
mergeSort(arr, left, middle, temp); // 排左半部分
|
|
mergeSort(arr, middle + 1, right, temp); // 排右半部分
|
|
merge(arr, left, middle, right, temp); // 合并两个已排部分
|
|
}
|
|
}
|
|
// 打印数组
|
|
void printArray(int arr[], int size) {
|
|
for (int i = 0; i < size; i++)
|
|
printf("%d ", arr[i]);
|
|
printf("\n");
|
|
}
|
|
|
|
int main() {
|
|
int arr[] = {8, 7, 6, 15, 4, 3, 2, 10};
|
|
int arrSize = sizeof(arr) / sizeof(arr[0]);
|
|
int temp[arrSize];
|
|
printf("原始数组: ");
|
|
printArray(arr, arrSize);
|
|
mergeSort(arr, 0, arrSize - 1, temp);
|
|
printf("排序后的数组: ");
|
|
printArray(arr, arrSize);
|
|
return 0;
|
|
} |