合并排序(非递归算法)

时间:2021-09-17 01:14:06
 

合并排序(非递归算法)

#include <stdio.h>//定义全局数组大小
int size=7;
void mergeSort(int a[]);
void mergePass(int x[],int y[],int s);
void merge(int c[],int d[],int l,int m,int r);
void mergeSort(int a[]){
   
    int *b=new int[size];
    int s=1;
    while(s<size){
        mergePass(a,b,s); //合并到数组b
        s+=s;
        mergePass(b,a,s); //合并到数组a
        s+=s;
    }
    delete [] b;
}
 
//-------------------------------------
// 对相邻为s的一段序列排序
// 3  6  4  12  8   5   14
// [3,6] [4,12] [5,8] [14]
// [3,4,6,12][5,8,14]
// [3,4,5,6,8,12,14]
//
//-------------------------------------
void mergePass(int x[],int y[],int s){
   
    //合并大小为s的相邻数组
   
    int i=0;
    while(i<=(size-2*s)){
        //合并大小为s 的相邻二段子数组
        merge(x,y,i,i+s-1,i+2*s-1);
        i=i+2*s;
    }
    //剩下的元素个数小于2s
    if((i+s)<size)
        merge(x,y,i,i+s-1,size-1);
    else
        //复制到y
        for(int j=i;j<size;j++)
            y[j]=x[j];
           
    return;
}
void merge(int c[],int d[],int l,int m,int r){
   
    //合并c[l:m]和c[m+1:r]到d[l:r]
    int i=l,j=m+1,k=l;
    while((i<=m)&& (j<=r))
        if(c[i]<=c[j])
            d[k++]=c[i++];
        else
            d[k++]=c[j++];
    if(i>m)
        for(int q=j;q<=r;q++)
            d[k++]=c[q];
   
    else
        for(int q=i;q<=m;q++)
            d[k++]=c[q];
           
}
 
void aprint(int b[])
{
 
    printf("size b :%d/n",size);
    for(int i=0;i<size;i++){
        printf("%d,",b[i]);
    }
}
 
 
void main(){
    int a[7]={3,6,4,12,8,5,14};
    mergeSort(a);
    aprint(a);
 
}
 
 
 
 
 
 
 
/* 二路归并排序算法的源程序*/
 
#include<stdio.h>
 
#define MAXNUM 100
#define TRUE 1
#define FALSE 0
 
typedef int KeyType;
typedef int DataType;
 
typedef struct {
    KeyType key;       /* 排序码字段 */
    /*DataType info;           记录的其它字段 */
} RecordNode;
 
typedef struct {
    int n;               /* n为文件中的记录个数,n<MAXNUM */
    RecordNode record[MAXNUM];
} SortObject;
 
void merge(RecordNode r[], RecordNode r1[], int low, int m, int high) {
    /* r[low]到r[m]和r[m+1]到r[right]是两个有序段 */
    int i = low, j = m + 1, k = low;
    
    while ( i <= m && j <= high ) {    /* 反复复制两个段的第一个记录中较小的 */
        if (r[i].key <= r[j].key)  
            r1[k++] = r[i++];
        else r1[k++] = r[j++];
    }
 
    while (i <= m) r1[k++] = r[i++];   /* 复制第一个段的剩余记录 */
    while (j <= high) r1[k++] = r[j++];/* 复制第二个段的剩余记录 */
 
}
 
/* 对 r 做一趟归并,结果放到 r1 中 */
void mergePass(RecordNode r[], RecordNode r1[], int n, int length) {
    int i = 0, j;                     /* length为本趟归并的有序子段的长度 */
 
    while(i + 2*length - 1 < n) {
        merge(r, r1, i, i+length-1, i + 2*length - 1);/* 归并长length的两个子段*/
        i += 2*length;
    }
    
    if(i + length - 1 < n - 1)        /* 剩下两段,后一段长度小于 length */
        merge(r, r1, i, i+length-1, n-1);
    else                              /* 将剩下的一段复制到数组r1 */
        for(j = i; j < n; j++) r1[j] = r[j];
}
 
void mergeSort(SortObject * pvector) {
    RecordNode record[MAXNUM];
    int length = 1;
 
    while (length < pvector->n) {
        /* 一趟归并,结果存放在数组record中*/
        mergePass(pvector->record, record, pvector->n, length);
        length *= 2;
        /* 一趟归并,结果存回 */
        mergePass(record, pvector->record, pvector->n, length);
        length *= 2;
    }
}
 
SortObject vector = {8, 49,38,65,97,76,13,27,49};
 
int main(){
    int i;
    mergeSort(&vector);
    for(i = 0; i < 8; i++)
        printf("%d ", vector.record[i]);
    getchar();
    return 0;
}