舉例講授C說話對合並排序算法的基本應用

舉例講授C說話對合並排序算法的基本應用。本站提示廣大學習愛好者：（舉例講授C說話對合並排序算法的基本應用）文章只能為提供參考，不一定能成為您想要的結果。以下是舉例講授C說話對合並排序算法的基本應用正文

基本概念
百度百科是這麼描寫合並排序的：
合並操作(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次

實例

#include <stdio.h> 
void printArr(int arr[],int length){ 
    int i; 
    for(i=0;i<length;i++){ 
        printf("%d,",arr[i]); 
    } 
    printf("\n"); 
} 
void merge(int a[],int alength,int b[],int blength,int c[]){//將2個已排好序的數組歸並到數組c 
    int i=0,j=0,k=0; 
    while(1){ 
        if(a[i]<=b[j]){ 
            c[k] = a[i]; 
            i++; 
            k++; 
            if(i==alength){ 
                for(;j<blength;j++,k++){ 
                    c[k] = b[j]; 
                } 
                break; 
            } 
        }else{ 
            c[k] = b[j]; 
            j++; 
            k++; 
            if(j==blength){ 
                for(;i<alength;i++,k++){ 
                    c[k] = a[i]; 
                } 
                break; 
            } 
        } 
    } 
    printArr(c,k); 
 
} 
void mergeSort(int arr[],int length){//將一個數組分紅2個數組，前length-1為第一個，最初一個為第二個，然後歸並2個數組 
    if(length > 1){ 
        int arr1[length-1],arr2[1] = {arr[length-1]}; 
        int i; 
        for(i=0;i<length-1;i++){ 
            arr1[i] = arr[i]; 
        } 
        mergeSort(arr1,length-1);//遞歸的挪用本身 
        merge(arr1,length-1,arr2,1,arr); 
    } 
} 
 
int main(void){ 
    int a[10] = {3,54,16,8,123,8,89,23,87,2}; 
    printArr(a,10); 
    mergeSort(a,10); 
    return 0; 
 
} 

算法機能/龐雜度
合並排序的效力是很高的，因為遞歸劃分為子序列只須要logN龐雜度，而歸並每兩個子序列須要年夜約2n次賦值，為O(n)龐雜度，是以，只須要簡略相乘便可獲得合並排序的時光龐雜度 O(㏒n)。而且因為合並算法是固定的，不受輸出數據影響，所以它在最好、最壞、均勻情形下表示簡直雷同，均為O(㏒n)。
然則，合並排序最年夜的缺點在於其空間龐雜度。從下面的代碼可以看到，在歸並子數組的時刻須要一個幫助數組，然後再把這個數據拷貝回原數組。所以，合並排序的空間龐雜度（額定空間）為O(n)。可弗成以省略這個數組呢？不可!假如撤消幫助數組而又要包管本來的數組中數據不被籠罩，那就必需要在數組中消費年夜量時光來挪動數據。不只輕易失足，還下降了效力。是以這個幫助空間是少不失落的。

算法穩固性
由於我們在碰到相等的數據的時刻必定是按次序“繕寫”到幫助數組上的，所以，合並排序異樣是穩固算法。

算法實用場景
合並排序在數據量比擬年夜的時刻也有較為精彩的表示（效力上），然則，其空間龐雜度O(n)使得在數據量特殊年夜的時刻（例如，1萬萬數據）簡直弗成接收。並且，斟酌到有的機械內存自己就比擬小，是以，采取合並排序必定要留意。