用c++编程实现:分别利用直接插入/折半插入/希尔/冒泡/快速/简单选择排序算法实现将待排序序列{3,6,2,10,1,20,88,8,5,7,4,9}由小到大排序,并输出结果。
时间: 2023-08-24 08:08:22 浏览: 100
好的,我可以帮你实现这个排序算法。以下是代码实现:
```c++
#include <iostream>
using namespace std;
void insertionSort(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 binaryInsertionSort(int arr[], int n) {
// 折半插入排序
for (int i = 1; i < n; i++) {
int key = arr[i];
int left = 0, right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
void shellSort(int arr[], int n) {
// 希尔排序
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
}
void bubbleSort(int arr[], int n) {
// 冒泡排序
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
// 快速排序
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void selectionSort(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]);
}
}
int main() {
int arr[] = {3, 6, 2, 10, 1, 20, 88, 8, 5, 7, 4, 9};
int n = sizeof(arr) / sizeof(arr[0]);
// 直接插入排序
insertionSort(arr, n);
cout << "直接插入排序结果:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 折半插入排序
binaryInsertionSort(arr, n);
cout << "折半插入排序结果:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 希尔排序
shellSort(arr, n);
cout << "希尔排序结果:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 冒泡排序
bubbleSort(arr, n);
cout << "冒泡排序结果:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 快速排序
quickSort(arr, 0, n - 1);
cout << "快速排序结果:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 简单选择排序
selectionSort(arr, n);
cout << "简单选择排序结果:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果如下:
```
直接插入排序结果:
1 2 3 4 5 6 7 8 9 10 20 88
折半插入排序结果:
1 2 3 4 5 6 7 8 9 10 20 88
希尔排序结果:
1 2 3 4 5 6 7 8 9 10 20 88
冒泡排序结果:
1 2 3 4 5 6 7 8 9 10 20 88
快速排序结果:
1 2 3 4 5 6 7 8 9 10 20 88
简单选择排序结果:
1 2 3 4 5 6 7 8 9 10 20 88
```
阅读全文