C语言程序设计 排序题

Question

将一个杂乱无序的整数序列，按照从小到大的顺序排列并输出。

题目虽然简单，但如果用教材介绍的9种方法都实现，还是需要一定的基本功和工作量的，希望大家2天左右完成。

注意：不能调用系统排序函数，源码中不要出现sort，自定义的也不行，换其它名字
测试数据不止一组，每组测试数据：

1）先输入无序序列的整数个数n；(n不超过1000000)

2）然后连续输入n个整数；

若n的值输入为0值，则输入结束
与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列．

注意：每组输出占一行
PS 9种方法为 直接插入排序 折半插入排序 希尔排序 冒泡排序 快速排序 简单选择排序 堆排序 归并排序 基数排序

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 QAQ
void 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+2
void 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

你要9种都实现吗？？？还是说挑一种？追问

谢谢你了、有位大大解决了我的问题。