C语言实现经典8大排序算法

#include stdio.h #include stdlib.h #define maxsize 100 void display(int a[],int n){ int i; for(i0;in;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(i0;in;i) scanf(%d,a[i]); printf(冒泡排序的结果为:\n); for(i0;in-1;i){ int flag0; for(j0;jn-1-i;j) { if(a[j]a[j1]) { tempa[j]; a[j]a[j1]; a[j1]temp; flag1; } } 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(i0;in;i) scanf(%d,a[i]); printf(选择排序的结果为:\n); for(i0;in-1;i){ int flag0; for(ji1;jn;j) { if(a[i]a[j]) { tempa[i]; a[i]a[j]; a[j]temp; } flag1; } 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(i0;in;i) scanf(%d,a[i]); printf(插入排序的结果为:\n); for(i1;in;i) { int flag0; tempa[i]; for(ji-1;tempa[j];j--) a[j1]a[j];//后移 a[j1]temp; flag1; 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(i0;in;i) scanf(%d,a[i]); printf(希尔排序的结果为:\n); for(gapn/2;gap0;gap/2){ int flag0; for(igap;in;i){ tempa[i]; for(ji;jgapa[j-gap]temp;j-gap){ a[j]a[j-gap]; } a[j]temp; flag1; } 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 n1mid-left1; int n2right-mid; int *L(int*)malloc(n1*sizeof(int)); int *R(int*)malloc(n2*sizeof(int)); for(i0;in1;i) L[i]a[lefti]; for(j0;jn2;j) R[j]a[mid1j]; i0; j0; kleft; while(in1jn2){ if(L[i]R[j]){ a[k]L[i]; i; } else { a[k]R[j]; j; } k; } while(in1){ a[k]L[i]; i; k; } while(jn2){ a[k]R[j]; j; k; } free(L); free(R); } // 归并排序递归函数 void mergeSort(int a[],int left,int right,int n) { if(leftright){ int midleft(right-left)/2; mergeSort(a,left,mid,n); mergeSort(a,mid1,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 i0;in;i) scanf(%d,a[i]); printf(归并排序的结果为:\n); mergeSort(a,0,n-1,n); } // 堆排序的堆调整函数 void heapify(int a[],int n,int i) { int largesti; int left2*i1; int right2*i2; int temp; if(leftna[left]a[largest]) largestleft; if(rightna[right]a[largest]) largestright; if(largest!i){ tempa[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(i0;in;i) scanf(%d,a[i]); printf(堆排序的结果为:\n); // 构建最大堆 for(in/2-1;i0;i--) heapify(a,n,i); display(a,n); // 一个个从堆顶取出元素 for(in-1;i0;i--){ tempa[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; }