内部排序算法比较(5)

数据结构课程设计

B[0]=mov; C[0]=t0; }

void bubblesort(SqList &L) //起泡排序 {

start_t=clock(); int i=1,j,com=0,mov=0; 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; mov+=3; } } i++; }

end_t=clock();

printf(\比较次数为 %d移动次数为 %d\\n\ t1=(double)(end_t-start_t)/CLK_TCK; printf(\排序用时为 %f\\n\ A[1]=com; B[1]=mov; C[1]=t1; }

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

start_t=clock();

19

数据结构课程设计

int i,j,com=0,mov=0; for(i=2;i<=L.length;i++) {

if(L.elem[i].key

L.elem[0].key=L.elem[i].key; mov++; j=i-1; com++;

while(L.elem[0].key

L.elem[j+1].key=L.elem[j].key; j--; mov++; com++; }

L.elem[j+1].key=L.elem[0].key; mov++; } }

end_t=clock();

printf(\比较次数为 %d移动次数为 %d\\n\ t2=(double)(end_t-start_t)/CLK_TCK; printf(\排序用时为 %f\\n\ A[2]=com; B[2]=mov; C[2]=t2; }

void xier(SqList &L) //希尔排序 {

start_t=clock();

int i,d=L.length/2,j,w=0,k,com=0,mov=0; while(w

20

数据结构课程设计

{ w=1;

for(i=w;i

for(j=i+d;j

if(L.elem[i].key>L.elem[j].key) { k=j; com++; } } 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; mov+=3; } w++; } d=d/2; w=1; }

end_t=clock();

printf(\比较次数为 %d移动次数为 %d\\n\ t3=(double)(end_t-start_t)/CLK_TCK; printf(\排序用时为 %f\\n\ A[3]=com; B[3]=mov; C[3]=t3; }

21

数据结构课程设计

void BeforeSort() {

yd1=0,bj1=0; }

void display(int m,int n) {

printf(\比较次数为 %d移动次数为 %d\\n\}

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

int pivotkey;

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

pivotkey=L.elem[low].key; while (low

while(low=pivotkey) { --high;

L.elem[low]=L.elem[high]; bj1++; yd1++; }

while (low

L.elem[high]=L.elem[low]; bj1++; yd1++; } }

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

22

数据结构课程设计

yd1++; return low; }

void QSort(SqList &L,int low,int high) {

int pivotloc; if(low

pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); } }

void QuickSort(SqList &L) {

start_t=clock(); BeforeSort(); QSort(L,1,L.length); display(bj1,yd1); end_t=clock();

t4=(double)(end_t-start_t)/CLK_TCK; printf(\排序用时为 %f\\n\ A[4]=bj1; B[4]=yd1; C[4]=t4; }

void Merge(ElemType R[],ElemType R1[],int low,int m,int high) //归并排序 {

int i=low, j=m+1, k=low; while(i<=m&&j<=high) {

if(R[i].key<=R[j].key) {

23