排序
Question one
/*
请设计直接插入排序算法函数void InsertSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 500000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void insertSort(int a[],int n)
{
int i, j;
for(i = 2; i < n; i++)//空出a[0]，并在初始时假设a[1]是有序的
{//插入排序不需要考虑最后一个数=
a[0] = a[i];
j = i - 1;//将a[0]和前面所有的数相比较
while(a[j] > a[0])
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = a[0];
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
insertSort(a,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
output(a,10);
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question two
/*
请设计二分插入排序算法函数void binInsertSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void binInsertSort(int a[],int n)
{
int mid, left, right, i, j;
for(i = 2; i < n; i++)
{
left = 1;//二分查找模板
right = i - 1;
while(left <= right)
{
mid = (left + right)/2;
if(a[i] < a[mid]) right = mid - 1;
else left = mid + 1;
}
a[0] = a[i];
for( j = i - 1; j >= left; j--) a[j + 1] = a[j];//后移一个位置
a[left] = a[0];
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
binInsertSort(a,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question three
/*
请设计shell排序算法函数void shellSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void shellSort(int a[],int n)
{
int i, j, d;
d = n/2;//主要是减少了小数在后带来的影响
while(d >= 1)
{
for(i = d + 1; i <= n; i++)//插入排序换皮版；
{
a[0] = a[i];
j = i - d;
while(j >= 1 && a[j] > a[0])
{
a[j + d] = a[j];
j = j - d;
}
a[j + d] = a[0];
}
d = d/2;
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
shellSort(a,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question four
/*
请设计简单选择排序算法函数void selectSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void selectSort(int a[],int n)
{
int i, j, min;
for(i = 1;i < n; i++)
{
min = i;//找到那个最下的数
for(j = i + 1; j <= n; j++)
if(a[min] > a[j])
min = j;
if(min != i)//如果不相等就交换两者的值
{
a[0] = a[i];
a[i] = a[min];
a[min] = a[0];
}
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
selectSort(a,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question five
/*
请设计筛选函数void sift(int a[],int k,int n)，对a[k] 进行筛选，
并利用其设计堆排序算法函数void heapSort(int a[],int n)，
对a[1]..a[n]进行升序排序。并测试在不同数据规模下的排序效率。（详见lab10_05.c）
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void sift(int a[],int k,int n)
{
int i,j,finished;
i=k;j=2*i;
a[0]=a[k];
finished=0;
while((j<=n)&&(!finished))
{
if((j<n)&&(a[j+1]>a[j]))
j++;
if(a[0]>=a[j])
finished=1;
else
{
a[i]=a[j];
i=j;j=2*j;
}
}
a[i]=a[0];
}
void heapSort(int a[],int n)
{
int i;
for (i=n/2;i>=1;i--)
sift(a,i,n);
for (i=n;i>1;i--)
{
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
sift(a,1,i-1);
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
heapSort(a,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question six
/*
请设计冒泡排序算法函数void bubbleSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void bubbleSort(int a[],int n)
{
int i, flag = 1;//flag用来判断结果是否是已经排好序的
while(flag == 1 && n > 1)
{
flag = 0;
for(i = 1; i < n; i++)
{
if(a[i] > a[i + 1])//交换
{
a[0] = a[i];
a[i] = a[i + 1];
a[i + 1] = a[0];
flag = 1;
}
}
n--;
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
bubbleSort(a,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question seven
/*
请设计快速排序算法函数void quickSort(int a[],int low,int right)，对a[low]..a[right]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
void exchange(int *a, int *b)
{
int num;
num = *a;
*a = *b;
*b = num;
}
/*请将本函数补充完整，并进行测试*/
void quick_sort(int a[], int low, int high)
{
if( low >= high) return;
int i = low - 1, j = high + 1, x = a[(low + high)/2];//初始化边界，最优的节点值为中间
while(i < j)//如果满足二分的条件就可以继续二分
{
do i++;while( a[i] < x);
do j--;while( a[j] > x);
if(i < j) exchange(&a[i], &a[j]);//找到两个满足条件的结果并交换
}
quick_sort(a, low, j);
quick_sort(a, j+1, high);
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
quick_sort(a,1,n);
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question eight
/*
请设计归并排序算法函数void mergeSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void merge(int a[],int u,int m,int v)
{ /*将有序段a[u..m],a[m+1..v]归并到a[u..v]*/
int i,j,k,t;
int b[N+1];
i=u; j=m+1; k=u;
while (i<=m && j<=v)
{
if(a[i]<=b[j] )
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
if (i>m)
for (t=j;t<=v;t++)
b[k+t-j]=a[t];
else
for (t=i;t<=m;t++)
b[k+t-i]=a[t];
/*将l2表中的内容拷贝回表l1*/
for (i=u;i<=v;i++)
a[i]=b[i];
}
/*----一趟归并------*/
int mergepass(int a[],int n,int len)
{ /*对a[1..n]进行长度为len的一趟并归*/
int i,t;
i=1;
while (i<=n-2*len+1)
{ merge(a,i,i+len-1,i+2*len-1);
i=i+2*len;
}
if (i+len-1<n)
merge(a,i,i+len-1,n);
}
/*----归并排序------*/
void mergeSort(int a[],int n)
{ int len, b[N+1];
len=1;
while (len<n)
{ mergepass(a,n,len);//从一开始不断扩大合并
len=len*2;
}
}
/*归并排序的递归实现*/
void mergeSortdc(int a[],int low,int high)
{
int mid;
if (low<high)
{
mid=(low+high)/2;
mergeSortdc(a,low,mid);//不断的划分成不能再划分
mergeSortdc(a,mid+1,high);
merge(a,low,mid,high);
}
}
int main()
{
int a[N+1],n; /*数据存储在a[1]...a[N]中*/
printf("数据初始化...\n");
n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("%d个数据排序中...\n",n);
mergeSort(a,n); /* 或调用mergeSortdc(a,1,n); */
saveData(a,n,"out.txt"); /*排序结果存放在out.txt文件中*/
printf("排序结束，排序结果保存在out.txt文件中。\n");
return 0;
}
Question nine
/*
请设计基于链表的基数排序函数void radixSort(linklist head)，对带头结点的整型非负单链表进行升序排序。
并测试在不同数据规模下的排序效率。(注：链表中的最大整数为500000)
*/
#include "slnklist.h"
struct node2
{
linklist front,rear;
};
#define N 1000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/
/*请将本函数补充完整，并进行测试*/
void radixSort(linklist head)
{
struct node2 q[10];/*队列*/
linklist p,r;
int i,j,k,x;
for (j=0;j<10;j++)
q[j].rear=q[j].front=NULL;
for (i=0;i<6;i++) //排序的最大数为6位数，共进行6趟分配收集过程
{
p=head->next; //分配
while (p)
{
head->next=p->next;
x=p->info;
for (j=0;j<i;j++)
x=x/10;
k=x%10; //取出本次按位分配的值
if (q[k].front==NULL) //队列为空
{
q[k].front=q[k].rear=p;
}
else //队列不为空
{
q[k].rear->next=p;
q[k].rear=p;
}
p=head->next;
}
//收集
r=head; //r为链尾指针
for (j=0;j<10;j++)
{
if (q[j].front!=NULL)
{ r->next=q[j].front;
r=q[j].rear;
q[j].front=q[j].rear=NULL;
}
}
r->next=NULL;
}
}
int main()
{
linklist head;
printf("数据初始化...\n");
head=creatLink("data1.txt",N); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
printf("数据排序中...\n");
radixSort(head);
writetofile(head,"out.txt"); /*排序结果保存在out.txt中*/
delList(head);
return 0;
}
版权声明：本文为pythpnhh原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。