排序算法c語言描述

排序算法系列學習，主要描述冒泡排序，選擇排序，直接插入排序，希爾排序，堆排序，歸並排序，快速排序等排序進行分析。

文章規劃：

一。通過自己對排序算法本身的理解，對每個方法寫個小測試程序。 具體思路分析不展開描述。

二。通過《大話數據結構》一書的截圖，詳細分析該算法 。

六。歸並排序
一。個人理解
歸並（Merge）排序法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。

所以歸並排序的核心在於先分解，再合並。

其基本思路就是將數組分成二組A，B，如果這二組組內的數據都是有序的，那麼就可以很方便的將這二組數據進行排序。

那麼如何讓這二個數組組內數據有序呢？

可以將A，B組各自再分成二組。依次類推，當分出來的小組只有一個數據時，可以認為這個小組組內已經達到了有序，然後再合並相鄰的二個小組就可以了。這樣通過先遞歸的分解數列，再合並數列就完成了歸並排序。

好了，下面就是具體操作過程：

1) 將n個元素分成各含n/2個元素的子序列

2)用歸並排序法對這兩個子序列遞歸地排序

3)合並這兩個已經排序好的子序列得到排序結果

歸並排序的大致內容就是這樣，如果有什麼不理解，可以具體看下面的《大話數據結構》一書截圖，具體不再重復。

直接上代碼。

#include<stdio.h>

#define Max_ 10
// 打印結果
void Show(int  arr[], int n)
{
    int i;
    for ( i=0; i<n; i++ )
        printf("%d  ", arr[i]);
    printf("\n");
}

// 歸並排序中的合並算法
void Merge(int array[], int left, int m, int right)
{
    int aux[Max_] = {0};  // 臨時數組 （若不使用臨時數組，將兩個有序數組合並為一個有序數組比較麻煩）
    int i; //第一個數組索引
    int j; //第二個數組索引
    int k; //臨時數組索引
    
    for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分別將 i, j, k 指向各自數組的首部。
    {
        //若 i 到達第一個數組的尾部，將第二個數組余下元素復制到 臨時數組中
        if (i == m+1)
        {
            aux[k] = array[j++];
            continue;
        }
        //若 j 到達第二個數組的尾部，將第一個數組余下元素復制到 臨時數組中
        if (j == right+1)
        {
            aux[k] = array[i++];
            continue;
        }
        //如果第一個數組的當前元素 比 第二個數組的當前元素小，將 第一個數組的當前元素復制到 臨時數組中
        if (array[i] < array[j])
        {
            aux[k] = array[i++];
        }
        //如果第二個數組的當前元素 比 第一個數組的當前元素小，將 第二個數組的當前元素復制到 臨時數組中
        else
        {
            aux[k] = array[j++];
        }
    }
    
    //將有序的臨時數組 元素 刷回 被排序的數組 array 中，
    //i = left , 被排序的數組array 的起始位置
    //j = 0， 臨時數組的起始位置
    for (i = left, j = 0; i <= right; i++, j++)
    {
        array[i] = aux[j];
    }
}

// 歸並排序
void MergeSort(int array[], int start, int end)
{
    if (start < end)
    {
        int i;
        i = (end + start) / 2;
        // 對前半部分進行排序
        MergeSort(array, start, i);
        // 對後半部分進行排序
        MergeSort(array, i + 1, end);
        // 合並前後兩部分
        Merge(array, start, i, end);
    }
}

int main()
{   //測試數據
    int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
    //排序前數組序列
    Show( arr_test, Max_ );
    MergeSort( arr_test, 0, Max_-1 );
    //排序後數組序列
    Show( arr_test, Max_ );
    return 0;
}