内部排序算法实现与性能分析课程设计

4、详细设计：

4.1函数调用关系图

开始界面 起 泡 排 序 各排序输出结果 各种排序用时比较 直插 排 序 选择 排 序 希尔排 序 快速 排 序 起泡 排 序 用时 直插 排 序 用时 选择 排 序 用时 希尔 排 序 用时 快速 排 序 用时 5、各个算法实现的源程序：

5.1、冒泡排序及其主要算法

void qipao(SqList &L)//起泡 {

start_t=clock(); int i=1,j;

while(i

for(j=1;j

if(L.elem[j].key>L.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; }

第 9 页 共 14 页

}

i++; }

5.2、直接插入排序及其主要算法

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

start_t=clock(); int i,j;

for(i=2;i<=L.length;i++) {

if(L.elem[i].key<=L.elem[i-1].key)//“<”，需将L.r[i]插入有序子序列 {

L.elem[0].key=L.elem[i].key; //复制为哨兵

j=i-1;

while(L.elem[0].key

L.elem[j+1].key=L.elem[j].key; //记录后移 j--; }

L.elem[j+1].key=L.elem[0].key; //插入到正确位置 } }

5.3、选择排序及其主要算法

void SelectSort(SqList &L)//选择 {

int i,j,k,;

for(i=1;i

for(j=i+1;j

if(L.elem[j].key<=L.elem[k].key) {

L.elem[0].key=L.elem[i].key; L.elem[i].key=L.elem[k].key;

L.elem[k].key=L.elem[0].key;//与第i个记录交换 } }

第 10 页 共 14 页

5.4、希尔排序及其主要算法

void xier(SqList &L)//希尔排序并打印结果 { start_t=clock(); int i,d=L.length/2,j,w=0,k,yd=0,bj=0; //间长为d while(wL.elem[j].key) { k=j; bj++; 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; } } } } d=d/2;//间隔变为原来 的一半 }

5.5、快速排序及其主要算法

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

int pivotkey;

L.elem[0]=L.elem[low]; yd1++;

pivotkey=L.elem[low].key; //用子表的第一个记录作曲轴记录 while (low

yd1++;

while(low=pivotkey) --high;

第 11 页 共 14 页

L.elem[low]=L.elem[high]; //将比轴记录小的记录交换到低端 while (low

L.elem[high]=L.elem[low]; //将比轴记录大的记录交换到高端 }

L.elem[low]=L.elem[0];

return low; //返回曲轴所在位置 }

void QSort(SqList &L,int low,int high) { //对顺序表L.r[low..high]做快速排序 int pivotloc; int i=1;

if(low

pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二 QSort(L,low,pivotloc-1); //对低字表递归排序 QSort(L,pivotloc+1,high); //对高字表递归排序 } }

void QuickSort(SqList &L) { //对顺序表L做快速排序 int j;

BeforeSort();

QSort(L,1,L.length); for(j=1;j<=L.length;j++) printf(\ display(yd1,bj1); }

6、调试分析：

1．产生随机数

第 12 页 共 14 页