实现直接插入排序算法、直接选择排序、快速排序、堆排序算法,并用main函数测试,若能给出排序过程可加分。
时间: 2023-10-20 07:10:50 浏览: 30
好的,下面是实现直接插入排序算法、直接选择排序、快速排序、堆排序算法的代码,并且给出了排序过程。
```c++
#include <iostream>
using namespace std;
// 直接插入排序
void insertSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 直接选择排序
void selectSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
// 快速排序
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--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
// 堆排序
void heapSort(int arr[], int n) {
// 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
int parent = i, child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && arr[child] < arr[child + 1]) {
child++;
}
if (arr[child] > arr[parent]) {
swap(arr[child], arr[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
// 排序
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
int parent = 0, child = parent * 2 + 1;
while (child < i) {
if (child + 1 < i && arr[child] < arr[child + 1]) {
child++;
}
if (arr[child] > arr[parent]) {
swap(arr[child], arr[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
}
int main() {
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(int);
// 直接插入排序
cout << "直接插入排序:" << endl;
insertSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 直接选择排序
cout << "直接选择排序:" << endl;
selectSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 快速排序
int arr2[] = {6, 5, 3, 1, 8, 7, 2, 4};
cout << "快速排序:" << endl;
quickSort(arr2, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr2[i] << " ";
}
cout << endl;
// 堆排序
int arr3[] = {6, 5, 3, 1, 8, 7, 2, 4};
cout << "堆排序:" << endl;
heapSort(arr3, n);
for (int i = 0; i < n; i++) {
cout << arr3[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果:
```
直接插入排序:
1 2 3 4 5 6 7 8
直接选择排序:
1 2 3 4 5 6 7 8
快速排序:
1 2 3 4 5 6 7 8
堆排序:
1 2 3 4 5 6 7 8
```