数据结构之排序的实现

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);//组合，将两个有序区归并为一个有序区
    }
}