排序之归并操作

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
　　如　设有数列{6，202，100，301，38，8，1}
　　初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数
　　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3
　　i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4
　　i=3　[ 1 6 8 38 100 202 301 ] 4
　　总计：　11次
 
c语言实现如下：
[cpp]  
#include <stdio.h>  
#include <string.h>  
#include <malloc.h>  
  
void display(int array[],int size){  
        printf("the array is:");  
        int i;  
        for(i=0;i<size;i++){  
                printf("%d ",array[i]);  
        }  
        printf("\n");  
}  
  
//将a数组中first开始mid结束的数组，mid+1开始last结束的数组 进行合并，再存放回a中  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
  
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
  
    while (i <= m)  
        temp[k++] = a[i++];  
  
    while (j <= n)  
        temp[k++] = a[j++];  
  
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  
  
void sort(int a[], int first, int last, int temp[]){  
        if (first < last)  
    {  
        int mid = (first + last) / 2;  
    //左侧的数组进行排序  
        sort(a, first, mid, temp);  
    //右侧的数组进行排序  
        sort(a, mid + 1, last, temp);  
    //将左右数组进行合并  
        mergearray(a, first, mid, last, temp);  
    }  
}  
  
int main(void){  
        int array[10]={34,45,1,39,21,68,65,100,4,51};  
        display(array,10);  
    //申请临时数组，用于存放合并的数组  
        int* temp = (int *)malloc(sizeof(int)*10);  
        memset(temp,0,10);  
    //归并算法函数  
        sort(array,0,10-1,temp);  
    free(temp);  
    temp = null;  
        display(array,10);  
        return 0;  
}  
 
 
 

补充：软件开发 , C++ ,

上一个：310 - L--system
下一个：C/C++拾遗录--for循环中的三语句执行顺序