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

while(j>0) { t++;

if(b[j].key>b[j+gap].key) {

x=b[j];b[j]=b[j+gap]; b[j+gap]=x;j=j-gap; s+=3; }

else j=0; gap=gap/2; }}

cout<<\移动次数=\比较次数=\}}

//选择排序

void gentsort(int b[],int n) {

int i,j,k; int s=0,t=0;

for(i=0;i

k=i;

for(j=i+1;j

if(b[k]>b[j]) {k=j;} }

if(k!=i)

{int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; }}

cout<<\移动次数=\比较次数=\}

//快速排序

void output(sqlist b,int n)//输出元素值 {

for(int i=0;i

cout<

void display(int n,int m)//输出计数 {

cout<<\移动次数=\比较次数=\}

void BeforeSort()//初始化计数器 {

p=0;q=0; }

void quicksort(sqlist r,int s,int t) {

int i=s,j=t; if(s

r[0]=r[s];p++; while(i

while(i=r[0].key) j--; r[i]=r[j]; q++; p++;

p++;

while(i

r[j]=r[i];q++;p++; }

r[i]=r[0];p++; } else return;

quicksort(r,s,j-1); quicksort(r,j+1,t); }

void sort(sqlist r,int s,int t) {

BeforeSort();

quicksort(r,s,t); display(p,q); }

//2-路插入排序

void sort3(sqlist nu,int n)

{//int max=n; #define max 20

int first,final;//头尾指针

int cache[max+1];//中转站

int i,j,s=0;//i,j循环变量 k计数器 int t=0;

for(i=0;i

if(0==i) {

first=0;

final=0;

cache[0]=nu[0].key; }

else {

if(nu[i].key>=cache[final])

{t++;

final++;

cache[final]=nu[i].key;

s++; }

else if(nu[i].key<=cache[first])

{t++;

if(first==0)first=n;

first--;

cache[first]=nu[i].key;

s++; }

else

{ t++;

for(j=first;nu[i].key>cache[j];)

{

if(0==j)

cache[n-1]=cache[0];

else

cache[j-1]=cache[j];

s++;j++;

if(j==n)j=0;

}

if(0==first)first=n-1;