用C语言编写用C语言编写程序,应用归并排序算法,对一个为n的记录序列a1,a2,…,an-1,an进行升序排序。
时间: 2024-09-29 09:08:17 浏览: 42
在C语言中,我们可以使用归并排序算法对数组进行升序排序。归并排序是一种分治策略,它将大问题分解成小问题然后递归地解决,最后再合并结果。
以下是使用C语言实现归并排序的一个基本步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 函数声明
void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int left, int right);
// 合并两个已排序的部分
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组
int L[n1], R[n2];
// 将两部分复制到临时数组
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
// 合并临时数组
i = 0; // 初始化L指针
j = 0; // 初始化R指针
k = l; // 初始化arr指针
while (i < n1 && j < n2) {
if (L[i] <= R[j]) { // 如果L的元素小于等于R的元素
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 将剩余元素(如果有的话)从L或R添加到arr
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序函数
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// 找出中间位置
int mid = left + (right - left) / 2;
// 分割数组并对左半部分和右半部分分别进行排序
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并左右两个已经排序的部分
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {5, 2, 8, 3, 9, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
mergeSort(arr, 0, n - 1);
printf("After sorting:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
运行这个程序会将输入的整数数组按升序排列。
阅读全文