合并排序(非递归算法)
#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;
}