编写程序分别采用直接插入排序算法 、折半插入排序算法、冒泡排序算法、快速排序算法,实现对任意一组整型数据(无序)的递增排序,分别输出各算法的每趟排序结果。
时间: 2023-07-18 11:43:36 浏览: 109
下面是分别采用直接插入排序算法、折半插入排序算法、冒泡排序算法、快速排序算法对整型数据进行递增排序并输出每趟排序结果的示例代码:
```c
#include <stdio.h>
// 直接插入排序算法
void insertSort(int arr[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
// 输出每趟排序结果
printf("第 %d 趟排序结果:", i);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
// 折半插入排序算法
void binaryInsertSort(int arr[], int n) {
int i, j, tmp, low, high, mid;
for (i = 1; i < n; i++) {
tmp = arr[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > tmp) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (j = i - 1; j >= high + 1; j--) {
arr[j + 1] = arr[j];
}
arr[high + 1] = tmp;
// 输出每趟排序结果
printf("第 %d 趟排序结果:", i);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
// 冒泡排序算法
void bubbleSort(int arr[], int n) {
int i, j, tmp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
// 输出每趟排序结果
printf("第 %d 趟排序结果:", i + 1);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
// 快速排序算法
int partition(int arr[], int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotPos = partition(arr, low, high);
// 输出每趟排序结果
printf("第 %d 趟排序结果:", pivotPos + 1);
for (int k = 0; k <= high; k++) {
printf("%d ", arr[k]);
}
printf("\n");
quickSort(arr, low, pivotPos - 1);
quickSort(arr, pivotPos + 1, high);
}
}
int main() {
int arr[] = {6, 3, 8, 1, 5};
int n = sizeof(arr) / sizeof(int);
printf("直接插入排序算法:\n");
insertSort(arr, n);
printf("\n折半插入排序算法:\n");
binaryInsertSort(arr, n);
printf("\n冒泡排序算法:\n");
bubbleSort(arr, n);
printf("\n快速排序算法:\n");
quickSort(arr, 0, n - 1);
return 0;
}
```
在上述示例代码中,我们定义了四个排序算法:直接插入排序算法、折半插入排序算法、冒泡排序算法和快速排序算法。在每个排序算法的实现中,我们都加入了输出每趟排序结果的代码。在主函数中,我们首先创建一个整型数组 `arr`,并存储需要排序的数据。然后,我们分别调用四个排序算法对数组进行递增排序,并输出每趟排序结果。
需要注意的是,快速排序算法中我们采用了递归的方式实现排序,因此在输出每趟排序结果时,我们需要将排序过程进行拆分,对每个子序列都输出一次排序结果。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)