帮我写一个C语言结构体的归并排序
时间: 2023-09-16 20:05:31 浏览: 82
### 回答1:
归并排序是一种分治算法,其思想是将一个数组分成两个子数组,对子数组进行排序,然后将排序后的子数组合并成一个有序数组。
下面是 C 语言中结构体的归并排序的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义结构体
struct Student {
char name[20];
int age;
};
// 归并排序函数
void merge_sort(struct Student *arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
// 合并两个有序数组
int i = left, j = mid + 1, k = 0;
struct Student *tmp = (struct Student *)malloc((right - left + 1) * sizeof(struct Student));
while (i <= mid && j <= right) {
if (arr[i].age < arr[j].age) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= right) tmp[k++] = arr[j++];
for (i = 0; i < k; i++) arr[left + i] = tmp[i];
free(tmp);
}
int main() {
// 初始化数组
struct Student arr[] = {
{"Tom", 18},
{"Bob", 20},
{"Alice", 19},
{"John", 17},
};
int n = sizeof(arr) / sizeof(arr[0]);
// 调用归并排序函数
merge_sort(arr, 0, n - 1);
// 输出排序后的数组
for (int i = 0; i < n; i++) {
printf("%s %d\n", arr[i].name, arr[i].age);
}
return 0;
}
```
在上面的代码中,我们定义了一个名为 `Student` 的结构体,包含两个字段:`name` 和 `age`。
### 回答2:
归并排序(Merge Sort)是一种经典的排序算法,它通过将数组分成左右两个子数组进行递归排序,然后再将两个有序子数组进行合并,最终得到一个有序的完整数组。
在C语言中,可以通过结构体来实现归并排序。首先,定义一个结构体来表示要排序的元素,其中包含需要排序的数据和用于排序的辅助数组。然后,编写归并排序函数来操作这个结构体。
下面是一个使用结构体实现归并排序的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
} Element;
void merge(Element array[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
Element *leftArray = (Element*)malloc(n1 * sizeof(Element));
Element *rightArray = (Element*)malloc(n2 * sizeof(Element));
for (i = 0; i < n1; i++) {
leftArray[i] = array[left + i];
}
for (j = 0; j < n2; j++) {
rightArray[j] = array[mid + 1 + j];
}
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (leftArray[i].data <= rightArray[j].data) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
array[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
free(leftArray);
free(rightArray);
}
void mergeSort(Element array[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
int main() {
int i;
Element array[6] = { {9}, {3}, {6}, {2}, {8}, {5} };
int n = sizeof(array) / sizeof(array[0]);
mergeSort(array, 0, n-1);
printf("排序后的结果:");
for (i = 0; i < n; i++) {
printf("%d ", array[i].data);
}
return 0;
}
```
以上代码是一个使用结构体实现归并排序的示例,其中定义了一个`Element`结构体来表示要排序的数据,使用`mergeSort`函数对数组进行归并排序,并输出排序后的结果。可以根据具体需求进行修改和扩展。
### 回答3:
归并排序是一种经典的排序算法,它将数组逐渐分割为更小的子数组,然后将这些子数组按照顺序合并,最终得到一个有序的数组。下面是使用C语言实现归并排序的结构体示例代码:
```c
#include <stdio.h>
typedef struct {
int* arr; // 存储待排序数组的指针
int length; // 待排序数组的长度
} MergeData;
void merge(int* arr, int left, int mid, int right) {
int temp[right - left + 1]; // 临时数组,用于存储合并后的结果
int i = left, j = mid + 1, k = 0; // 分别表示左侧子数组的起始索引、右侧子数组的起始索引和临时数组的索引
// 合并左右两个子数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) { // 左侧元素小于等于右侧元素
temp[k++] = arr[i++];
} else { // 右侧元素小于左侧元素
temp[k++] = arr[j++];
}
}
// 将未处理完的剩余元素依次放入临时数组
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的结果复制回原数组
for (i = left, k = 0; i <= right; ++i, ++k) {
arr[i] = temp[k];
}
}
void mergeSort(int* arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // 求中间索引
mergeSort(arr, left, mid); // 对左侧子数组进行递归排序
mergeSort(arr, mid + 1, right); // 对右侧子数组进行递归排序
merge(arr, left, mid, right); // 合并两个有序的子数组
}
}
int main() {
int arr[] = {5, 2, 8, 3, 1, 7, 6, 4};
int length = sizeof(arr) / sizeof(arr[0]);
MergeData data = {arr, length};
mergeSort(data.arr, 0, data.length - 1);
printf("排序结果:");
for (int i = 0; i < data.length; ++i) {
printf("%d ", data.arr[i]);
}
printf("\n");
return 0;
}
```
以上是一个简单的利用归并排序算法对数组进行排序的示例代码。在merge函数中,它将两个有序子数组合并为一个有序数组,并在mergeSort函数中,通过递归调用不断划分子数组直到达到基本情况,然后再逐层合并子数组,最终得到整个数组的有序结果。在main函数中,我们创建了一个待排序的数组,然后调用mergeSort函数对其进行排序,并输出排序结果。
希望对你有帮助!