合并排序(非递归算法)

#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;      

}