大数据结构课程设计—内部排序算法比较

实用标准文案

void Merge(datatype R[ ], datatype R1[ ], int s, int m , int t)//归并排序 {

int i,j,k;

i=s; j=m+1; k=s; while (i<=m&&j<=t) {

cn[4]++;

if(R[i].key

{ R1[k++]=R[i++]; mn[4]++;} else { R1[k++]=R[j++]; mn[4]++;} }

while (i<=m) { R1[k++]=R[i++]; mn[4]++; } while (j<=t) { R1[k++]=R[j++]; mn[4]++;} }

void MSort(datatype R[ ], datatype R1[ ], int s, int t)//归并排序 {

int m;

if(s==t) { R1[s]=R[s]; mn[4]++;} else {m=(s+t)/2;

MSort(R, R1, s, m); MSort(R, R1, m+1, t); Merge(R1, R, s, m, t); } }

void MergeSort(datatype R[ ], datatype R1[ ], int n)//归并排序** {

MSort(R, R1,1, n); }

int Partition(datatype R[ ], int low, int high) {

R[0]=R[low]; mn[5]++; while(low=R[0].key) {cn[5]++; high--;} if(low

while(low

R[low]=R[0]; mn[5]++; return low;

精彩文档

实用标准文案

}

void erlucharu(datatype R[ ],datatype d[ ],int n)//2路排序 {

//元素0是哨兵。

//int length = count -1;

//int R[count] = {0, 49, 38, 65, 97, 76, 13, 27, 49}; //对顺序表R作2-路插入排序。 //d[n] = { 0 };

d[0].key = R[1].key;//R中D的第一个记录为d中排好序的记录。 cn[9]++;

int first = 0, final = 0;//first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。

for (int i = 2; i <= n; ++i)//依次将R的第2个～最后一个记录插入d中。 { cn[9]++;

if (R[i].key < d[first].key)//待插入记录小于d中最小值，插入到d[first]之前（不需移动d数组的元素）。 {

first = (first - 1 + n) % n; d[first].key = R[i].key; cn[9]++; mn[9]+=2; }

else if (R[i].key > d[final].key)//待插入记录大于d中最小值，插入到d[final]之后（不需移动d数组的元素）。 { cn[9]+=2;

final = final + 1;

d[final].key = R[i].key; mn[9]+=2; }

else//待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素）。 { cn[9]+=2;

int j = final ++;//移动d尾部元素以便按序插入记录。 while (R[i].key < d[j].key) { cn[9]++;

d[(j + 1) % n].key = d[j].key; j = (j - 1 + n) % n;

精彩文档

实用标准文案

mn[9]+=2; } cn[9]++;

d[j + 1].key = R[i].key; mn[9]+=2; } } cn[9]++; for ( i = 1; i <= n; i ++)//循环把d赋给R。 { cn[9]++;

R[i].key = d[(i + first - 1) % n].key;//线性关系。 mn[9]++; } cn[9]++; }

void Quick_Sort(datatype R[ ], int s, int t)//快速排序 {

int i; if( s

i = Partition(R, s, t); Quick_Sort(R, s, i-1); Quick_Sort(R, i+1, t); } }

void prin(datatype R[],int n) {

int i ;

printf(\排序的结果为：\ for(i=1;i<=n;i++) printf(\ \ printf(\

}

void sui_ji()//随机取数 {

int i,n;

datatype R[MAXNUM]={0};

精彩文档

实用标准文案

a: printf(\请输入你要输入的个数:\ scanf(\ if(n>25) {

printf(\超出范围重新输入!!!\\n\ goto a; } for(i=1;i<=n;i++) { R[i].key=1+(int)(1000.0*rand()/(RAND_MAX+1.0));//随机生成1000以内的整数 }

printf(\排序前元素顺序为:\ for(i=1;i

D_InsertSort(R,n);//直接排序 prin(R,n);

Select_Sort(R,n);//简单选择排序 Bubble_Sort(R, n);//冒泡排序 HeapSort(R, n);//堆排序

datatype R1[MAXNUM]={0};

MergeSort(R, R1, n);//二路归并排序 Quick_Sort(R,0, n);//快速排序 //ji_shu(R,n);//基数排序 Insert(R,n);//直接插入排序******* Zhe_ban(R,n);//折半插入排序****** erlucharu(R, R1,n);//2路排序*/ shell_sorts(R,n);//希尔排序 A(R,n); }

void zixing_input()//自行输入数字 { int n,i;

datatype R1[MAXNUM]={0};

printf(\请输入你要输入的个数（不大于于30的整数）:\

精彩文档