#include <stdio.h> #include <stdlib.h> #define maxsize 100 void display(int a[],int n){ int i; for(i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } void MP_sort(int a[],int n){//冒泡排序 int i,j,temp; printf("请输入数组元素个数:\n"); scanf("%d",&n); printf("录入数组:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("冒泡排序的结果为:\n"); for(i=0;i<n-1;i++){ int flag=0; for(j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; flag=1; } } if(!flag) break; display(a,n); } } void XZ_sort(int a[],int n){//选择排序 int i,j,temp; printf("请输入数组元素个数:\n"); scanf("%d",&n); printf("录入数组:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("选择排序的结果为:\n"); for(i=0;i<n-1;i++){ int flag=0; for(j=i+1;j<n;j++) { if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } flag=1; } if(!flag) break; display(a,n); } } void CR_sort(int a[],int n) {//插入排序 int i,j,temp; printf("输入数组元素个数:\n"); scanf("%d",&n); printf("录入数组:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("插入排序的结果为:\n"); for(i=1;i<n;i++) { int flag=0; temp=a[i]; for(j=i-1;temp<a[j];j--) a[j+1]=a[j];//后移 a[j+1]=temp; flag=1; if(!flag) break; display(a,n); } } // 希尔排序 void XE_sort(int a[],int n) { int i,j,temp,gap; printf("请输入数组元素个数:\n"); scanf("%d",&n); printf("录入数组:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("希尔排序的结果为:\n"); for(gap=n/2;gap>0;gap/=2){ int flag=0; for(i=gap;i<n;i++){ temp=a[i]; for(j=i;j>=gap&&a[j-gap]>temp;j-=gap){ a[j]=a[j-gap]; } a[j]=temp; flag=1; } if(!flag) break; display(a,n); } } // 快速排序的划分函数（显示每趟结果） int partition_display(int a[], int low, int high, int n) { int pivot = a[low]; // 选择第一个元素为基准 int i = low, j = high; int temp; while (i < j) { // 从右向左找第一个小于pivot的元素 while (i < j && a[j] >= pivot) { j--; } if (i < j) { a[i] = a[j]; // 将小于pivot的元素移到左边 i++; } // 从左向右找第一个大于等于pivot的元素 while (i < j && a[i] < pivot) { i++; } if (i < j) { a[j] = a[i]; // 将大于等于pivot的元素移到右边 j--; } } a[i] = pivot; // 基准元素放到最终位置 // 显示本趟排序结果 printf("基准 %d 排序后: ", pivot); for (int k = 0; k < n; k++) { printf("%d ", a[k]); } printf("\n"); return i; // 返回基准位置 } // 快速排序递归函数（显示每趟结果） void quickSort_display(int a[], int low, int high, int n) { if (low < high) { int pivotpos = partition_display(a, low, high, n); quickSort_display(a, low, pivotpos - 1, n); quickSort_display(a, pivotpos + 1, high, n); } } // 快速排序入口函数（显示每趟结果） void KS_sort(int a[], int n) { printf("请输入数组元素个数:\n"); scanf("%d", &n); printf("录入数组:\n"); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } printf("初始数组: "); display(a, n); printf("快速排序每趟结果:\n"); quickSort_display(a, 0, n-1, n); printf("最终排序结果: "); display(a, n); } // 归并排序的合并函数 void merge(int a[],int left,int mid,int right) { int i,j,k; int n1=mid-left+1; int n2=right-mid; int *L=(int*)malloc(n1*sizeof(int)); int *R=(int*)malloc(n2*sizeof(int)); for(i=0;i<n1;i++) L[i]=a[left+i]; for(j=0;j<n2;j++) R[j]=a[mid+1+j]; i=0; j=0; k=left; while(i<n1&&j<n2){ if(L[i]<=R[j]){ a[k]=L[i]; i++; } else { a[k]=R[j]; j++; } k++; } while(i<n1){ a[k]=L[i]; i++; k++; } while(j<n2){ a[k]=R[j]; j++; k++; } free(L); free(R); } // 归并排序递归函数 void mergeSort(int a[],int left,int right,int n) { if(left<right){ int mid=left+(right-left)/2; mergeSort(a,left,mid,n); mergeSort(a,mid+1,right,n); merge(a,left,mid,right); display(a,n); } } void GB_sort(int a[],int n) {//归并排序 printf("请输入数组元素个数:\n"); scanf("%d",&n); printf("录入数组:\n"); for(int i=0;i<n;i++) scanf("%d",&a[i]); printf("归并排序的结果为:\n"); mergeSort(a,0,n-1,n); } // 堆排序的堆调整函数 void heapify(int a[],int n,int i) { int largest=i; int left=2*i+1; int right=2*i+2; int temp; if(left<n&&a[left]>a[largest]) largest=left; if(right<n&&a[right]>a[largest]) largest=right; if(largest!=i){ temp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,n,largest); } } void D_sort(int a[],int n) {//堆排序 int i,temp; printf("请输入数组元素个数:\n"); scanf("%d",&n); printf("录入数组:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("堆排序的结果为:\n"); // 构建最大堆 for(i=n/2-1;i>=0;i--) heapify(a,n,i); display(a,n); // 一个个从堆顶取出元素 for(i=n-1;i>0;i--){ temp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,i,0); display(a,n); } } // 二叉排序树节点定义 typedef struct BSTNode { int data; struct BSTNode *left; struct BSTNode *right; } BSTNode; // 创建新节点 BSTNode* createNode(int data) { BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } // 向二叉排序树插入节点 BSTNode* insertBST(BSTNode* root, int data) { if (root == NULL) { return createNode(data); } if (data < root->data) { root->left = insertBST(root->left, data); } else { root->right = insertBST(root->right, data); } return root; } // 中序遍历二叉排序树（将结果存入数组） void inorderTraversal(BSTNode* root, int a[], int* index) { if (root != NULL) { inorderTraversal(root->left, a, index); a[(*index)++] = root->data; inorderTraversal(root->right, a, index); } } // 释放二叉排序树内存 void freeBST(BSTNode* root) { if (root != NULL) { freeBST(root->left); freeBST(root->right); free(root); } } // 二叉排序树排序 void BST_sort(int a[], int n) { int i; BSTNode* root = NULL; printf("请输入数组元素个数:\n"); scanf("%d", &n); printf("录入数组:\n"); for(i = 0; i < n; i++) scanf("%d", &a[i]); printf("二叉排序树排序的结果为:\n"); // 构建二叉排序树 for(i = 0; i < n; i++) { root = insertBST(root, a[i]); // 每次插入后显示当前树的中序遍历结果 int temp[maxsize]; int index = 0; inorderTraversal(root, temp, &index); printf("插入 %d 后的中序遍历: ", a[i]); display(temp, index); } // 最终的中序遍历结果就是排序结果 int index = 0; inorderTraversal(root, a, &index); printf("最终排序结果: "); display(a, n); // 释放内存 freeBST(root); } // 桶排序 void T_sort(int a[], int n) { int i, j, k; printf("请输入数组元素个数:\n"); scanf("%d", &n); printf("录入数组:\n"); for(i = 0; i < n; i++) scanf("%d", &a[i]); printf("桶排序的结果为:\n"); // 确定最大值和最小值 int min_val = a[0], max_val = a[0]; for(i = 1; i < n; i++) { if(a[i] < min_val) min_val = a[i]; if(a[i] > max_val) max_val = a[i]; } // 创建桶（这里使用10个桶） int bucket_count = 10; int bucket_size = n; int **buckets = (int**)malloc(bucket_count * sizeof(int*)); int *bucket_sizes = (int*)calloc(bucket_count, sizeof(int)); for(i = 0; i < bucket_count; i++) { buckets[i] = (int*)malloc(bucket_size * sizeof(int)); } // 将元素分配到桶中 double range = (double)(max_val - min_val + 1) / bucket_count; for(i = 0; i < n; i++) { int bucket_index = (int)((a[i] - min_val) / range); if(bucket_index >= bucket_count) bucket_index = bucket_count - 1; buckets[bucket_index][bucket_sizes[bucket_index]++] = a[i]; } // 显示每个桶的初始内容 printf("分配到桶后的情况:\n"); for(i = 0; i < bucket_count; i++) { printf("桶%d: ", i); if(bucket_sizes[i] == 0) { printf("空"); } else { for(j = 0; j < bucket_sizes[i]; j++) { printf("%d ", buckets[i][j]); } } printf("\n"); } // 对每个桶进行插入排序 for(i = 0; i < bucket_count; i++) { if(bucket_sizes[i] > 0) { // 对当前桶进行插入排序 for(j = 1; j < bucket_sizes[i]; j++) { int temp = buckets[i][j]; k = j - 1; while(k >= 0 && buckets[i][k] > temp) { buckets[i][k + 1] = buckets[i][k]; k--; } buckets[i][k + 1] = temp; } } } // 显示排序后每个桶的内容 printf("每个桶排序后的情况:\n"); for(i = 0; i < bucket_count; i++) { printf("桶%d: ", i); if(bucket_sizes[i] == 0) { printf("空"); } else { for(j = 0; j < bucket_sizes[i]; j++) { printf("%d ", buckets[i][j]); } } printf("\n"); } // 合并桶 int index = 0; for(i = 0; i < bucket_count; i++) { for(j = 0; j < bucket_sizes[i]; j++) { a[index++] = buckets[i][j]; } // 显示当前合并进度 printf("合并桶%d后的数组: ", i); display(a, index); } // 释放内存 for(i = 0; i < bucket_count; i++) { free(buckets[i]); } free(buckets); free(bucket_sizes); } int main(){ int a[maxsize]; int n; int choice; do{ printf("请输入你的选择:\n1.冒泡排序\n2.选择排序\n3.插入排序\n"); printf("4.希尔排序\n5.快速排序\n6.归并排序\n7.堆排序\n8.二叉排序树排序\n9.桶排序\n"); printf("0.退出程序！\n"); scanf("%d",&choice); switch(choice){ case 1: MP_sort(a,n);break; case 2: XZ_sort(a,n);break; case 3: CR_sort(a,n);break; case 4: XE_sort(a,n);break; case 5: KS_sort(a,n);break; case 6: GB_sort(a,n);break; case 7: D_sort(a,n);break; case 8: BST_sort(a,n);break; case 9: T_sort(a,n);break; case 0: printf("程序已退出!\n");break; default: printf("输入错误，请重新输入!\n");break; } }while(choice!=0); return 0; }
