请用C++实现堆排序与站排序
时间: 2023-12-30 09:03:53 浏览: 23
堆排序(Heap Sort):
```
#include <stdio.h>
// 调整堆
void adjustHeap(int arr[], int i, int len) {
int temp = arr[i];
int j = 2 * i + 1;
while (j < len) {
if (j + 1 < len && arr[j] < arr[j + 1]) {
j++;
}
if (arr[j] > temp) {
arr[i] = arr[j];
i = j;
j = 2 * i + 1;
} else {
break;
}
}
arr[i] = temp;
}
// 堆排序
void heapSort(int arr[], int len) {
// 构建最大堆
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len);
}
// 排序
for (int i = len - 1; i > 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
}
int main() {
int arr[] = { 5, 2, 9, 3, 7, 6, 8, 1, 4 };
int len = sizeof(arr) / sizeof(int);
heapSort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
快速排序(Quick Sort):
```
#include <stdio.h>
// 快速排序
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
int main() {
int arr[] = { 5, 2, 9, 3, 7, 6, 8, 1, 4 };
int len = sizeof(arr) / sizeof(int);
quickSort(arr, 0, len - 1);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```