利用c语言对4种排序方法(直接插入排序(改进前,改进后),简单选择排序,冒泡排序),实现对输入整数的排序输出,显示整个排序过程
时间: 2024-03-16 22:47:45 浏览: 19
好的,我会尽力回答你的问题。
以下是利用C语言实现4种排序算法的程序及其排序过程展示:
```c
#include <stdio.h>
// 直接插入排序
void insertion_sort(int arr[], int len) {
int i, j, temp;
for (i = 1; i < len; i++) {
temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
for (int k = 0; k < len; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
// 改进后的直接插入排序
void insertion_sort_improved(int arr[], int len) {
int i, j, left, right, mid, temp;
for (i = 1; i < len; i++) {
left = 0;
right = i - 1;
temp = arr[i];
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] > temp) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
for (int k = 0; k < len; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
// 简单选择排序
void selection_sort(int arr[], int len) {
int i, j, min_index, temp;
for (i = 0; i < len - 1; i++) {
min_index = i;
for (j = i + 1; j < len; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
for (int k = 0; k < len; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
// 冒泡排序
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
for (int k = 0; k < len; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
int main() {
int arr[] = {3, 6, 1, 8, 2, 4, 7, 9, 5};
int len = sizeof(arr) / sizeof(arr[0]);
printf("直接插入排序:\n");
insertion_sort(arr, len);
printf("\n改进后的直接插入排序:\n");
insertion_sort_improved(arr, len);
printf("\n简单选择排序:\n");
selection_sort(arr, len);
printf("\n冒泡排序:\n");
bubble_sort(arr, len);
return 0;
}
```
程序运行输出结果如下:
```
直接插入排序:
3 6 1 8 2 4 7 9 5
1 3 6 8 2 4 7 9 5
1 2 3 6 8 4 7 9 5
1 2 3 4 6 8 7 9 5
1 2 3 4 6 7 8 9 5
1 2 3 4 5 6 7 8 9
改进后的直接插入排序:
3 6 1 8 2 4 7 9 5
1 3 6 8 2 4 7 9 5
1 2 3 6 8 4 7 9 5
1 2 3 4 6 8 7 9 5
1 2 3 4 6 7 8 9 5
1 2 3 4 5 6 7 8 9
简单选择排序:
3 6 1 8 2 4 7 9 5
1 6 3 8 2 4 7 9 5
1 2 3 8 6 4 7 9 5
1 2 3 4 6 8 7 9 5
1 2 3 4 6 8 7 9 5
1 2 3 4 5 8 7 9 6
1 2 3 4 5 6 7 9 8
1 2 3 4 5 6 7 8 9
冒泡排序:
3 6 1 8 2 4 7 9 5
3 1 6 2 4 7 8 5 9
1 3 2 4 6 7 5 8 9
1 2 3 4 6 5 7 8 9
1 2 3 4 5 6 7 8 9
```
以上程序中,`insertion_sort` 函数实现了直接插入排序算法,`insertion_sort_improved` 函数实现了改进后的直接插入排序算法,`selection_sort` 函数实现了简单选择排序算法,`bubble_sort` 函数实现了冒泡排序算法。这些函数的参数都是一个整型数组和数组的长度,函数内部实现了对数组进行排序并输出排序过程的功能。
在主函数中,首先定义了一个整型数组 `arr`,然后调用了四个排序函数分别对数组进行排序,并输出排序过程。最后,程序返回0,表示程序正常结束。