数据结构之排序的实现

1、插入排序

?

void InsertSort(RecType R[],int n){    int i,j,k;    RecType temp;    for (i=1; i<n; i++) {        temp=R[i];        j=i-1;        while (j>=0&&temp.key<R[j].key) {            R[j+1]=R[j];            j--;        }        R[j+1]=temp;          printf("    i=%d  ",i);       for (k=0; k<n; k++) {           printf("%3d",R[k].key);        }        printf("\n");    }    }

?2、冒泡排序

?

void BubbleSort(RecType R[],int n){    int i,j,k;    RecType temp;    for (i=0; i<n-1; i++) {        for (j=n-1; j>i; j--) {            if(R[j].key<R[j-1].key){                temp=R[j];                R[j]=R[j-1];                R[j-1]=temp;                        }        }        printf("  i=%d:    ",i);        for (k=0; k<n; k++) {            printf("%2d",R[k].key);        }        printf("\n");    }}

?

3、选择排序

?

void SelectSort(RecType R[],int n){    int i,j,k;    RecType temp;    for (i=0; i<n-1; i++) {        k=i;        for (j=i+1; j<n; j++) {            if(R[j].key<R[k].key){                k=j;            }        }        if(k!=i){            temp=R[i];            R[i]=R[k];            R[k]=temp;        }        printf("  i=%d:    ",i);        for (k=0; k<n; k++) {            printf("%2d",R[k].key);        }        printf("\n");    }}

?4、希尔排序

?

void ShellSort(RecType R[],int n){    int i,j,d,k;    RecType temp;    d=n/2;    while (d>0) {        for (i=d; i<n; i++) {            j=i-d;            while (j>=0&&R[j].key>R[j+d].key) {                temp=R[j];                R[j]=R[j+d];                R[j+d]=temp;                j=j-d;            }        }          printf("  d=%d:    ",d);       for (k=0; k<n; k++) {           printf("%3d",R[k].key);       }       printf("\n");       d=d/2;  }}

?

5、快速排序

?

void QuickSort(RecType R[],int s,int t){    int i=s,j=t,k;    RecType temp;    if(s<t){        temp=R[s];        while(i!=j){            while(j>i&&R[j].key>temp.key)                   j--;            if(i<j){                R[i]=R[j];                i++;            }            while(i<j&&R[i].key<temp.key)                i++;            if(i<j){                R[j]=R[i];                j--;            }        }        R[i]=temp;        printf("      ");        for(k=0;k<10;k++){            if(k==i){                printf(" [%d]",R[k].key);            }else{                printf("%4d",R[k].key);            }        }        printf("\n");                QuickSort(R,s,i-1);        QuickSort(R,i+1,t);        }}

6、堆排序

?

void Sift(RecType R[],int low,int high){    int i=low,j=2*i;    RecType temp=R[i];    while(j<=high){        if(j<high&&R[j].key<R[j+1].key){            j++;        }        if(temp.key<R[j].key){            R[i]=R[j];            i=j;            j=2*i;        }else{            break;        }    }    R[i]=temp;}void HeapSort(RecType R[],int n){    int i;    RecType temp;    for(i=n/2;i>=1;i--)        Sift(R,i,n);    printf("初始堆： ");DispHeap(R,1,n);printf("\n");    for (i=n; i>=2; i--) {        printf("交换%d与%d,输出%d\n",R[i].key,R[1].key,R[1].key);        temp=R[1];        R[1]=R[i];        R[i]=temp;        Sift(R,1,i-1);        printf("筛选调整得到堆：");        DispHeap(R,1,i-1);        printf("\n");    }     }

?

7、归并排序

?

?

void Merge(RecType *R,int low,int m,int high){//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]    int i=low,j=m+1,p=0; //置初始值    RecType *R1; //R1是局部向量    R1=(RecType *)malloc((high-low+1)*sizeof(RecType));    if(!R1)return; //申请空间失败    while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上        R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];    while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中        R1[p++]=R[i++];    while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中        R1[p++]=R[j++];    for(p=0,i=low;i<=high;p++,i++)        R[i]=R1[p];//归并完成后将结果复制回R[low..high]}void MergeSort(RecType R[],int low,int high){//用分治法对R[low..high]进行二路归并排序    int mid;    if(low<high){//区间长度大于1        mid=(low+high)/2;//分解        MergeSort(R,low,mid);//递归地对R[low..mid]排序        MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序        Merge(R,low,mid,high);//组合，将两个有序区归并为一个有序区    }}