数据结构课程设计_排序算法比较【完整版】

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

}//for return OK; }

/******************************************************************************** 希尔排序

*********************************************************************************/

//参考书P272算法10.4及10.5

/*Status ShellInsert(Sqlist &L,int dk) //希尔插入排序 { int i,j; //前后位置的增量是dk for(i=dk+1;i<=L.length;i++) //r[0]只是暂存单元，不是哨兵， { if(L.r[i]0 && L.r[0]

Status ShellSort(Sqlist &L,int dlta[5],int t) //希尔排序 { int i; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=0;i

第 11 页 共 20 页

//一趟增量 } return OK; } */

//************************************************************** // 起泡排序

//************************************************************** Status BubbleSort(Sqlist &L) { int i,j,t; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=1;i<=L.length-1;i++) { for(j=1;j<=L.length-i;j++) { if(L.r[j]>L.r[j+1]) //前面的数据>后面数据时 { t=L.r[j+1]; L.r[j+1]=L.r[j]; L.r[j]=t; //将元素交换 } } } return OK; }

//**************************************************** // 快速排序

//****************************************************

int Partition(Sqlist &L, int low, int high) //交换顺序表中子表L.r[low..high]的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大于它 { int pivotkey; //记录关键字 L.r[0]=L.r[low]; //用子表的第一个纪录作枢轴纪录 pivotkey=L.r[low]; //用枢轴纪录关键字 while (low=pivotkey)

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

{ high--; } L.r[low]= L.r[high]; //将比枢轴记录小的记录移到低端 while(low

L.r[low]=L.r[0]; //枢轴记录到位 return low; }//Partition函数

void Qsort (Sqlist &L,int low, int high) { int pivotloc; if (low

Status QuickSort (Sqlist &L) {

if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } Qsort(L,1,L.length); return OK; }//QuickSort

//********************************************** // 选择排序

//********************************************** Status ChooseSort(Sqlist &L) { int i,j,k,t; if(L.length==0) { printf(\没有数据！\ return ERROR;

第 13 页 共 20 页

} for(i=1;i<=L.length;i++) //排序的趟数 { k=i; for(j=i+1;j<=L.length;j++) //比较第i个元素以及其后的数据中最小的 { if(L.r[j]

//**************************************** // 堆排序

//****************************************

Status HeapAdjust(Sqlist &L,int s,int m) //调整L.r[s]的关键字,使L.r[s~m]成大顶堆 { int i; L.r[0]=L.r[s]; for(i=2*s;i+1<=m;i*=2) //沿数据较大的孩子结点向下筛选 { if(i=L.r[i]) //L.r[0]插入在S位置上 break; L.r[s]=L.r[i]; s=i; } L.r[s]=L.r[0]; //插入新数据 return OK; }

Status HeapSort(Sqlist &L) //堆排序 { int i,t;

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

if(L.length==0) { printf(\没有数据！\ return ERROR; } for(i=L.length/2;i>0;i--) HeapAdjust(L,i,L.length); for(i=L.length;i>1;i--) { t=L.r[1]; //将堆顶记录和当前未经排序的子序列L.r[1..i]中最后一个记录互换 L.r[1]=L.r[i]; L.r[i]=t; HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆 } return OK; }

//************************************************** // 基数排序

//************************************************** typedef struct node{ int key; node *next; }RecType;

Status RadixSort(Sqlist L) { int t,i,j,k,d,n=1,m; RecType *p,*s,*q,*head[10],*tail[10]; //定义各链队的首尾指针 for(i=1;i<=L.length;i++) //将顺序表转化为链表 { s=(RecType*)malloc(sizeof(RecType)); s->key=L.r[i]; if(i==1) //当为第一个元素时 { q=s; p=s; t++; } else { q->next=s; //将链表连接起来 q=s; t++;

第 15 页 共 20 页