排序算法-歸并排序(MergeSort)-C

思路：

使用分治思想，将問題分成一些小問題然後遞歸求解，再将各個小問題的解歸并到一起。

使用遞歸，将一個數組不斷分為兩個更小的子數組，遞歸對更小的子數組排序。然後将已排序的兩個子數組合并到一個新數組（這裡需要額外使用一個同樣大小的新數組），再将排序好的新數組中的元素拷貝回原數組。

基本操作是合并兩個已經排序的數組，使用三個計數器Apos，Bpos，Cpos 初始值分别位三個數組的A,B,C的開始位置，比較A[Apos]和B[Bpos]的大小，并将較小者輸出到C[Cpos ],然後計數器增加。當兩個數組A和B有一個為空，則将另一個數組剩餘部分拷貝到C中。

如果在merge方法中聲明一個臨時數組，由于merge會被遞歸調用很多次，在遞歸期間就會生成很多臨時數組，占用一部分記憶體；另一個方面，在聲明數組的過程中調用malloc 和free 配置設定并釋放記憶體，也會占用一些時間。是以這裡在排序算法的驅動程式中就申請一個同樣大小的臨時數組，在後面遞歸調用merge方法中共享使用。

時間複雜度：

平均：

  ，最好：

，最壞：

程式：

void merge(int array[],int tmp_array[],int left,int center,int right)
{
    int i,left_pos,right_pos,tmp_pos,length;
    length=right-left+1;
    left_pos=left;
    right_pos=center+1;
    tmp_pos=left;
    while(left_pos<=center&&right_pos<=right)          //将兩個數組中的較小者輸出到第三個數組
        if(array[left_pos]<array[right_pos])
            tmp_array[tmp_pos++]=array[left_pos++];
        else
            tmp_array[tmp_pos++]=array[right_pos++];

    while(left_pos<=center)                            //将第一個數組中剩餘元素拷貝到第三個數組
        tmp_array[tmp_pos++]=array[left_pos++];
    while(right_pos<=right)
        tmp_array[tmp_pos++]=array[right_pos++];       //将第二個數組中剩餘元素拷貝到第三個數組 

    for(i=0;i<length;i++)                              //将第三個數組中的元素拷貝回原數組中
        array[left+i]=tmp_array[left+i];
}

void merge_sort_recurise(int array[],int tmp_array[],int left,int right)
{
    int center;
    if(left<right)
    {
        center=(left+right)/2;
        merge_sort_recurise(array,tmp_array,left,center);
        merge_sort_recurise(array,tmp_array,center+1,right);
        merge(array,tmp_array,left,center,right);
    }
}

void merge_sort(int array[],int array_size)
{
    int *tmp_array=calloc(array_size,sizeof(int));
    if(tmp_array==NULL)
    {
        printf("No full space for array!\n");
        return;
    }
    merge_sort_recurise(array,tmp_array,0,array_size-1);
    free(tmp_array);
}
           

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i;  
    int array[]={100,96,88,75,63,52,41,36,28,19,6,0,-19,-105};
    int array_size=sizeof(array)/sizeof(int);
    printf("Original array:\n");
    for(i=0;i<array_size;i++)
        printf(" %d, ",array[i]);
    printf("\n");
    merge_sort(array,array_size);
    printf("Sorted array:\n");
    for(i=0;i<array_size;i++)
        printf(" %d, ",array[i]);
    printf("\n");
    return 0;
}
           

參考：

https://www.cnblogs.com/onepixel/p/7674659.html

https://www.runoob.com/w3cnote/merge-sort.html