楼主 看到你的问题后我写到现在。。满意的话请采纳 QAQ
输入数据的时候每个数字之间用回车隔开。
也可以修改一下用随机数放到数组中
#include <stdio.h>#include <stdlib.h>#include <time.h>#define RADIX_10 10 //整形排序#define KEYNUM_31 10 //关键字个数,这里为整形位数void swap(int * a, int * b);//交换两个数void inputnum(int * a, int n); //输入数组里的数字void showarray(int * a, int n); //显示数组数据int paixu(int * a, int n); //不要吐槽名字 因为不让用sort QAQvoid straight_insert_sort(int * a, int n); //直接插入排序void bin_insert_sort(int * a, int n); //折半查找排序void ShellSort(int* pDataArray, int iDataNum); //希尔排序void ShellInsert(int* pDataArray, int d, int iDataNum); //一趟希尔排序void quickSort(int a[],int left,int right);//快速排序void selectSort(int a[], int n); //简单选择排序void MinheapsortTodescendarray(int a[], int n);//堆排序void MinHeapFixdown(int a[], int i, int n);void MakeMinHeap(int a[], int n);void RadixSort(int* pDataArray, int iDataNum);//基数排序int GetNumInPos(int num,int pos);int main (void){ int n; int *a; printf("请输入数据个数n = "); scanf("%d", &n); while (n != 0) { a = (int *)malloc((n+1) * sizeof(int)); inputnum(a, n); //输入数据 showarray(a, n); paixu(a, n); //数组排序 showarray(a, n); //输出数组 free(a); printf("\n请输入数据个数n = "); scanf("%d", &n); } return 0;}//输入数字到数组void inputnum(int * a, int n){ int i; srand(time(NULL)); for (i = 1; i <= n; i++) { scanf("%d", &a[i]); //a[i] = rand()%200; }}//输出数组void showarray(int * a, int n){ int i; for (i = 1; i <= n; i++) { printf("%d ", a[i]); }}void straight_insert_sort(int *a, int n){ int i; int j; for (i = 2; i <= n; i++) { if (a[i] < a[i-1]) { a[0] = a[i]; a[i] = a[i-1]; for (j = i - 2; a[0] < a[j]; j--) { a[j+1] = a[j]; } a[j+1] = a[0]; } }}void bin_insert_sort(int * a, int n) //折半查找排序{ int low, high, mid, i, j; for (i = 2; i <= n; i++) { a[0] = a[i]; low = 1; high = i-1; while (low <= high) { mid = (low + high) / 2; if (a[0] < a[mid]) { high = mid - 1; } else { low = mid + 1; } } for (j = i - 1; j >= high + 1; j--) { a[j+1] = a[j]; } a[high + 1] = a[0]; }}/*********************************************************函数名称:ShellInsert*参数说明:pDataArray 无序数组;* d 增量大小* iDataNum为无序数据个数*说明: 希尔按增量d的插入排序*********************************************************/void ShellInsert(int* pDataArray, int d, int iDataNum){ int i, j, temp; for (i = d; i < iDataNum; i += 1) //从第2个数据开始插入 { j = i - d; temp = pDataArray[i]; //记录要插入的数据 while (j >= 0 && pDataArray[j] > temp) //从后向前,找到比其小的数的位置 { pDataArray[j+d] = pDataArray[j]; //向后挪动 j -= d; } if (j != i - d) //存在比其小的数 pDataArray[j+d] = temp; }}/*********************************************************函数名称:ShellSort*参数说明:pDataArray 无序数组;* iDataNum为无序数据个数*说明: 希尔排序*********************************************************/void ShellSort(int* pDataArray, int iDataNum){ int d; d = iDataNum / 2; //初始增量设为数组长度的一半 while(d >= 1) { ShellInsert(pDataArray, d, iDataNum); d = d / 2; //每次增量变为上次的二分之一 }}//冒泡排序void BubbleSort(int a[], int n){ int i, j; for (i = 1; i <= n; i++) for (j = 2; j <= n - i; j++) if (a[j - 1] > a[j]) { a[0] = a[j]; a[j] = a[j-1]; a[j-1] = a[0]; }}//快速排序void quickSort(int a[],int left,int right){ int i=left; int j=right; int temp=a[left]; if(left>=right) return; while(i!=j) { while(i<j&&a[j]>=temp) j--; if(j>i) a[i]=a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位 while(i<j&&a[i]<=temp) i++; if(i<j) a[j]=a[i]; } a[i]=temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys quickSort(a,left,i-1);/*递归左边*/ quickSort(a,i+1,right);/*递归右边*/}void selectSort(int a[], int n) //简单选择排序{ int i, j, k, t; for(i=1;i<=n;i++) { k=i; for(j=i+1;j<=n;j++) { if(a[k]>a[j])k=j; } if(k!=i) {t=a[i];a[i]=a[k];a[k]=t;}}}void MinheapsortTodescendarray(int a[], int n){ int i; for (i = n - 1; i >= 1; i--) { swap(&a[i], &a[0]); MinHeapFixdown(a, 0, i); }}void swap(int *a, int * b)//交换两个数{ int x; x = *a; *a = *b; *b = x;}//建立最小堆void MakeMinHeap(int a[], int n){ int i; for (i = n / 2 - 1; i >= 0; i--) MinHeapFixdown(a, i, n);}// 从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2void MinHeapFixdown(int a[], int i, int n){ int j, temp; temp = a[i]; j = 2 * i + 1; while (j < n) { if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的 j++; if (a[j] >= temp) break; a[i] = a[j]; //把较小的子结点往上移动,替换它的父结点 i = j; j = 2 * i + 1; } a[i] = temp;}void over_array(int * a, int n){ int x; int i = 1; while (i <= n) { x = a[i]; a[i] = a[n]; a[n] = x; n--; i++; }}//将有二个有序数列a[first...mid]和a[mid...last]合并。void mergearray(int a[], int first, int mid, int last, int temp[]){ int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i];}void mergesort(int a[], int first, int last, int temp[]){ if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左边有序 mergesort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //再将二个有序数列合并 }}int MergeSort(int a[], int n){ int *p = malloc(sizeof(int)*n); if (p == NULL) return 0; mergesort(a, 0, n - 1, p); free(p); return 1;}/*********************************************************函数名称:GetNumInPos*参数说明:num 一个整形数据* pos 表示要获得的整形的第pos位数据*说明: 找到num的从低到高的第pos位的数据*********************************************************/int GetNumInPos(int num,int pos){ int i; int temp = 1; for (i = 0; i < pos - 1; i++) temp *= 10; return (num / temp) % 10;}/*********************************************************函数名称:RadixSort*参数说明:pDataArray 无序数组;* iDataNum为无序数据个数*说明: 基数排序*********************************************************/void RadixSort(int* pDataArray, int iDataNum){ int i, pos, j , k; int *radixArrays[RADIX_10]; //分别为0~9的序列空间 for (i = 0; i < 10; i++) { radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1)); radixArrays[i][0] = 0; //index为0处记录这组数据的个数 } for (pos = 1; pos <= KEYNUM_31; pos++) //从个位开始到31位 { for (i = 0; i < iDataNum; i++) //分配过程 { int num = GetNumInPos(pDataArray[i], pos); int index = ++radixArrays[num][0]; radixArrays[num][index] = pDataArray[i]; } for (i = 0, j =0; i < RADIX_10; i++) //收集 { for (k = 1; k <= radixArrays[i][0]; k++) pDataArray[j++] = radixArrays[i][k]; radixArrays[i][0] = 0; //复位 } }}int paixu(int * a, int n){ int i; printf("\n请输入排序方法:\n"); printf("1. 直接插入排序 \n"); printf("2. 折半插入排序 \n"); printf("3. 希尔排序 \n"); printf("4. 冒泡排序 \n"); printf("5. 快速排序 \n"); printf("6. 简单选择排序 \n"); printf("7. 堆排序 \n"); printf("8. 归并排序 \n"); printf("9. 基数排序 \n"); scanf("%d", &i); switch (i) { case 1: straight_insert_sort(a, n);break; case 2: bin_insert_sort(a, n); break; case 3: ShellSort(a+1, n); break; case 4: BubbleSort(a, n); break; case 5: quickSort(a, 1, n); break; case 6: selectSort(a, n); break; case 7: MakeMinHeap(a+1, n);MinheapsortTodescendarray(a+1, n); over_array(a, n); break; case 8: MergeSort(a+1, n);break; case 9: RadixSort(a+1, n);break; default: return 0; } return 1;}
满意请采纳。
温馨提示:答案为网友推荐,仅供参考