用C语言写一个分别用堆排序及快速排序算法,对待排序记录进行排序并输出排序结果的代码
时间: 2024-05-10 14:17:58 浏览: 5
下面是使用堆排序和快速排序算法对待排序记录进行排序并输出排序结果的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 堆排序
void heapSort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 从堆顶开始取出元素,依次放入有序区间末尾
for (int i = n - 1; i >= 0; i--) {
// 将堆顶元素放入有序区间末尾
swap(&arr[0], &arr[i]);
// 对剩余元素重新构建最大堆
heapify(arr, i, 0);
}
}
// 快速排序
void quickSort(int arr[], int left, int right) {
// 左右指针相遇,排序结束
if (left >= right)
return;
// 选取基准元素
int pivot = arr[(left + right) / 2];
// 分区
int i = left, j = right;
while (i <= j) {
// 在左边找到第一个大于等于基准元素的元素
while (arr[i] < pivot)
i++;
// 在右边找到第一个小于等于基准元素的元素
while (arr[j] > pivot)
j--;
// 如果左右指针未相遇,则交换这两个元素
if (i <= j) {
swap(&arr[i], &arr[j]);
i++;
j--;
}
}
// 递归排序左右两个子区间
quickSort(arr, left, j);
quickSort(arr, i, right);
}
// 交换元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 构建最大堆
void heapify(int arr[], int n, int i) {
int largest = i; // 最大元素的下标
int left = 2 * i + 1; // 左子节点下标
int right = 2 * i + 2; // 右子节点下标
// 在左右子节点中找到最大的元素
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大元素不是父节点,则交换它们,并递归地调整其子节点
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// 输出数组元素
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {5, 3, 8, 6, 4, 2, 9, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组:");
printArray(arr, n);
// 堆排序
heapSort(arr, n);
printf("堆排序结果:");
printArray(arr, n);
// 快速排序
quickSort(arr, 0, n - 1);
printf("快速排序结果:");
printArray(arr, n);
return 0;
}
```
输出结果:
```
原始数组:5 3 8 6 4 2 9 1 7
堆排序结果:1 2 3 4 5 6 7 8 9
快速排序结果:1 2 3 4 5 6 7 8 9
```