内部排序算法的实现与比较

内部排序算法的实现与比较

#include\ #include\ #include\ #include\ #include\ using namespace std; using std::cout; using std::endl;

void MergeSort(int r[],int r1[],int s,int t); void Merge(int r[],int r1[],int s,int m,int t); #define LIST_INIT_SIZE 50000

int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n; 为记录关键字比较和移动的次数 typedef struct { int key; }ElemType; typedef struct { ElemType *elem; int length; }SqList;

void addlist(SqList &L)//初始化顺序表 { a:

printf(\请输入你要输入的个数:\ scanf(\ if(n>50000) { printf(\超出范围重新输入!!!\\n\ goto a; }

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(0); }

void random(SqList &L)//随机数产生程序 { L.length=0;

//yd，bj static bool first=true; if(first) { srand(time(0)); first=false; }//使输入相同个数时每次产生的随机数不同 for(int i=1;i30000) goto a; ++L.length; } }

void memory(SqList &M,SqList &L)//记录L，使每个排序算法都用一组相同的随机数 { M.length=0; for(int i=1;i

void BubbleSort(SqList &L)//冒泡排序 { int i,j; for(i=1;iL.elem[j+1].key) { L.elem[0].key=L.elem[j].key; L.elem[j].key=L.elem[j+1].key; L.elem[j+1].key=L.elem[0].key; yd1+=3; } } } }

void InsertSort(SqList &L)//直接插入排序

{ int i,j; for(i=2;i<=L.length;i++) { if(L.elem[i].key

void SelectSort(SqList &L)//选择排序 { int i,j,k; for(i=1;i

int Partition(SqList &L,int low,int high)//快速排序 { int pivotkey;

L.elem[0]=L.elem[low]; yd4++; pivotkey=L.elem[low].key; while (low=pivotkey) --high; L.elem[low]=L.elem[high]; bj4++; yd4++; while (low

void QSort(SqList &L,int low,int high) //对顺序表的子序列作快速排序 { int pivotloc; if(low

void QuickSort(SqList &L) //对顺序表L作快速排序 { QSort(L,1,L.length); }

void ShellSort(SqList &L)//希尔排序 { int i,d=L.length/2,j,w=0,k; while(w

for(i=w;iL.elem[j].key) { k=j; bj5++; } } if(i!=k) { L.elem[0].key=L.elem[i].key; L.elem[i].key=L.elem[k].key; L.elem[k].key=L.elem[0].key; yd5+=3; } w++; } d=d/2; w=1; } }

void MergePass(SqList &L)//归并排序 {

int r[5000],r1[5000],s=0,t,k; k=L.length; t=k-1;

MergeSort(r,r1,0,t);//调用方法MergeSort() }

void MergeSort(int r[],int r1[],int s,int t) {

if(s==t)r1[s]=r[s]; else { int m=(s+t)/2; MergeSort(r,r1,s,m);//递归调用 MergeSort(r,r1,m+1,t); Merge(r1,r,s,m,t);//调用方法 Merge() } }

void Merge(int r[],int r1[],int s,int m,int t) {