Question

C语言程序设计 排序题

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

题目虽然简单，但如果用教材介绍的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种都实现吗？？？还是说挑一种？

追问

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