C语言排序题

Question

排序

[ Submit Code ] [ Top 20 Runs ]
Acceteped : 781 Submit : 1992
Time Limit : 1000 MS Memory Limit : 65536 KB

Description

N个整数，将其排序输出。
输入
第一行是一个整数K（1<=K<=20），表示有多少个样例，每个样例的第一行是一个整数N（1<=N<=1,000）和一个字符X，X为A时表示升序排序，为D时为降序排列；第二行为N个整数，每个整数都可以使用int表示，每个之间用一个空格隔开。
输出
每个样例输出一行，按排序要求输出整数，每个整数之间输出一个空格。（最后一个整数后不要有空格）

Sample Input

2
3 A
3 5 2
4 D
2 5 7 3

Sample Output

2 3 5
7 5 3 2
（不知道怎么才能在完成所有的数据输入以后同时输出这两组数据
2 3 5
7 5 3 2.
我只会输入一组数据然后立刻输出答案，再接着输入另一组数据
）
求高手指点，不胜感激！
在线等。。。望高手指导本菜鸟

Answer 1

楼主 看到你的问题后我写到现在。。满意的话请采纳 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;}
满意请采纳。

Answer 2

既然你会写排序算法，那么就给你个主函数的写法参考一下吧：
struct sample {
    int count; // 一个样例中的数据个数
    int *data; // 一组数据
    char order; // 排序方式
};
main()
{
    int nSample;
    int i, j;
    struct sample *sp;
    scanf("%d", &nSample); // 取得样例个数
    sp = (struct sample *)malloc(nSample*sizeof(struct sample));
    for(i = 0; i < nSample; i++) {
        scanf("%d %c", &sp[i].count, &sp[i].order);
        sp[i].data = (int *)malloc(sp[i].count * sizeof(int));
        for(j = 0; j < sp[i].count; j ++)
            scanf("%d", &sp[i].data[j])
        // 调用排序算法，排序算法的具体实现略
        order(sp);
    }
    // 将排序结果一起输出
    for(i = 0; i < nSample; i++) {
        printf("%d", sp[i].data[0]);
        for(j = 1;  j < sp[i].count; j++)
            printf(" %d", sp[i].data[j]);
        printf("\n");
    }
    // 释放分配的内存
    for(i = 0; i < nSample; i++)
        free(sp[i].data);
    free(sp);
}

追问

谢谢你辛苦写这些了。让我慢慢看看，好好研究下啊

本回答被提问者和网友采纳

Answer 3

应该就是输入一组数据之后立刻输出答案吧。因为是按照一组一组的测试用例来的。所以我觉得你并没有错啊追问

不是的呢，学校的网站上要求的都是先把数据全部输入，然后一次输出所有结果的，你仔细看样例输出的格式就知道了