【排序算法】—— 歸并排序（C語言）

一、歸并排序的原理

歸并排序（MergeSort） 是建立在歸并操作上的一種有效的排序算法，采用分治法排序，分為分解、合并兩個步驟。

分解：將數(shù)組分割成兩個數(shù)組，再分別將兩個數(shù)組又細分成2個數(shù)組，直到，最后每個數(shù)組都是一個元素，這時將該單元素數(shù)組看為有序數(shù)組

合并：將分割的有序數(shù)組進行排序，排成有序數(shù)組后繼續(xù)為上一個分割它的數(shù)組合并，直到數(shù)組被合并成原來的數(shù)組，此時已經(jīng)排好序了

二、兩個有序數(shù)組排序和合并

1. 原地排序

從頭到尾遍歷，選最小值放前面

1. 合并的兩個數(shù)組是一個數(shù)組分割開的，所以它們的首尾是相連的，用箭頭i指向合并后數(shù)組的當前下標位置

2. 將2和1比較，1小，所以將1賦值給合并后數(shù)組的第一個元素，此時我們發(fā)現(xiàn)，數(shù)組arr1的首元素被覆蓋，所以不能直接賦值

3. 若是將arr1的元素向后挪動一格，則數(shù)據(jù)正常，但是效率太低，不可取

從后往前遍歷，選最大值放后面

1. 用箭頭i指向合并后數(shù)組的后邊，從后往前遍歷

2. 8比7大，賦值給i指向的位置，此時7被覆蓋，不行

3. 若是將7和8交換呢，看樣子可以，那如果是如下數(shù)組就不行了，arr1的有序性被破壞，不能繼續(xù)這樣排序了

2. 創(chuàng)建臨時空間

1. 既然無法原地排序，那我們創(chuàng)建臨時空間，對兩個有序數(shù)組排序

2. 從前往后遍歷，選出最小值放在temp數(shù)組前面部分

3. 直到排序完成，將temp數(shù)組中的數(shù)據(jù)拷貝回原數(shù)組，arr1和arr2就合并成為有序數(shù)組arr

二、遞歸實現(xiàn)

我們使用遞歸來實現(xiàn)數(shù)組的分割和合并，它的邏輯非常像二叉樹的后序遍歷，由于我們要使用遞歸，又要申請臨時空間，所以我們先申請好臨時空間，再將歸并排序過程作為子函數(shù)調(diào)用，這樣不用在每次遞歸過程申請釋放空間

歸并排序調(diào)用遞歸

void MergeSort(int* arr, int size)
{
	int* temp = (int*)malloc(size * sizeof(int));
	if (temp == NULL)
	{
		perror("malloc fail\n");
		return;
	}

	_MergeSort(arr, 0, size - 1, temp);	//歸并排序的過程

	free(temp);
	temp = NULL;
}

歸并排序

由于我們遞歸過程中要用區(qū)間來分割函數(shù)，所以參數(shù)為待排數(shù)組的閉區(qū)間，使代碼書寫更加方便，這也是將遞歸過程單獨調(diào)用的好處

void _MergeSort(int* arr, int left, int right, int* temp)
{
    //分解：
    //分割數(shù)組只有一個元素時停止遞歸
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) / 2;

	_MergeSort(arr, left, mid, temp);		//分割并排序數(shù)組左半邊
	_MergeSort(arr, mid + 1, right, temp);	//分割并排序數(shù)組右半邊

    //合并：
	int begin1 = left, end1 = mid;			//數(shù)組1的左右區(qū)間
	int begin2 = mid + 1, end2 = right;		//數(shù)組2的左右區(qū)間
	int i = begin1;

    //排序兩個有序數(shù)組
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			temp[i] = arr[begin1];
			begin1++;
		}
		else
		{
			temp[i] = arr[begin2];
			begin2++;
		}
		i++;
	}

	while (begin1 <= end1)
	{
		temp[i] = arr[begin1];
		begin1++;
		i++;
	}

	while (begin2 <= end2)
	{
		temp[i] = arr[begin2];
		begin2++;
		i++;
	}

	//拷貝臨時數(shù)組的內(nèi)容到原數(shù)組（可以調(diào)用memcpy函數(shù)）
	//memcpy(arr+left, temp+left, (right-left+1)*sizeof(int));
	for (i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

三、非遞歸實現(xiàn)

歸并排序的非遞歸實現(xiàn)是非常復雜的一個算法，在快速排序中我們使用棧來存儲待排數(shù)組的左右區(qū)間，模擬遞歸的過程。但是在歸并排序中我們不這么實現(xiàn)。

1. 實現(xiàn)思路

由于數(shù)組總是以一半的方式進行分割，分割的終點是每個數(shù)組只有一個元素，所以我們可以定義一個變量gap作為分割后數(shù)組的長度，遍歷時一次跳過gap * 2個元素，剛好是兩個數(shù)組的長度，gap從1開始對兩個有序數(shù)組進行排序，直到gap作為數(shù)組長度的一半時結束

1. 令gap = 1，此時將長度為1的數(shù)組排序并合并，將兩個長度為1的數(shù)組合并（黃色和藍色分別是需要合并的兩個數(shù)組）

2. 排序合并后，將i指針向后移動gap * 2個元素，剛好兩個數(shù)組，繼續(xù)排序合并

3. 持續(xù)上述操作，直到數(shù)組排序完成，則第一躺排序完成，所有長度為1的有序數(shù)組都合并成長度為2的有序數(shù)組

4. gap *= 2，一個數(shù)組長度為2，然后遍歷數(shù)組，一次跳過2個有序數(shù)組（4個元素），并將兩個有序數(shù)組排序合并

5. gap *= 2，一個數(shù)組長度為4，然后遍歷數(shù)組，一次跳過2個有序數(shù)組（8個元素），并將兩個有序數(shù)組排序合并

6. gap *= 2，此時gap為8，等于數(shù)組長度，意味著沒有第二個數(shù)組與長度為8的數(shù)組合并了，排序結束，數(shù)組有序

2. 數(shù)組邊界問題

在歸并排序的非遞歸實現(xiàn)中，我們要遍歷數(shù)組，將兩個長度為gap的數(shù)組排序合并，但是gap總是2的冪次方，這就導致數(shù)組長度不一定是gap * 2的倍數(shù)，這就導致兩個數(shù)組在遍歷到數(shù)組邊界時會導致越界問題。所以我們要對數(shù)組的邊界問題進行處理

對于歸并排序合并的兩個數(shù)組，有3種越界情況：

1. 第一個數(shù)組越界

黃色和藍色數(shù)組是需要合并的兩個數(shù)組，第一個數(shù)組指的是黃色數(shù)組，第二個數(shù)組指的是藍色數(shù)組

此時遍歷到數(shù)組末尾時，第一個數(shù)組只有一個元素，但是需要合并的數(shù)組長度是2，所以第一個數(shù)組訪問時會造成越界（第二個數(shù)組自然也越界）

2. 第二個數(shù)組全部越界

此時遍歷到數(shù)組末尾時，第一個數(shù)組的長度剛好到原數(shù)組的末尾，第二個數(shù)組不存在，訪問第二個數(shù)組是回越界

3. 第二個數(shù)組部分越界

此時第一個數(shù)組在數(shù)組內(nèi)，第二個數(shù)組只有一部分在數(shù)組內(nèi)，第二個數(shù)組存在但是長度沒有gap，訪問第二個數(shù)組時會越界

解決方法：

我們來解決這些數(shù)組越界問題的方法是調(diào)整數(shù)組區(qū)間范圍：

1. 第一個數(shù)組越界時，第二個數(shù)組不存在，所以不用合并，第一個數(shù)組本身就是有序數(shù)組
2. 第二個數(shù)組完全越界時，第二個數(shù)組依然不存在，所以不用合并
3. 第三個數(shù)部分組越界時，第二個數(shù)組存在但是不完整，此時我們將第二個數(shù)組的結束位置調(diào)整為原數(shù)組末尾位置即可，讓第一個數(shù)組和第二個數(shù)組合并。

3. 代碼實現(xiàn)

先申請臨時空間，然后根據(jù)gap遍歷數(shù)組，依次排序合并數(shù)組。文章來源地址http://www.zghlxwxcb.cn/news/detail-480357.html

void MergeSortNonR(int* arr, int size)
{
    //申請空間
    int* temp = (int*)malloc(size * sizeof(int));
    if (temp == NULL)
    {
        perror("malloc fail!\n");
        return;
    }
    
    //歸并排序
    int gap = 1;
    while (gap < size)
    {
        //單趟排序
        int i = 0;
        for (i = 0; i < size; i += 2*gap)	//一次跨2*gap格，兩個數(shù)組
        {
            int begin1 = i, end1 = i+gap-1;			//第一個數(shù)組下標區(qū)間
            int begin2 = i+gap, end2 = i+2*gap-1;	//第二個數(shù)組下標區(qū)間，別忘記加上i
            
            //數(shù)組邊界處理
            if (end1 >= size)	//第一個數(shù)組越界
            {
                break;
            }
            if (begin2 >= size)	//第二個數(shù)組全部越界
            {
                break;
            }
            if (end2 >= size)	//第二個數(shù)組部分越界
            {
                end2 = size - 1;
            }
            
            //排序合并
            int j = i;	//合并后數(shù)組的下標
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (arr[begin1] <= arr[begin2])
                {
                    temp[j] = arr[begin1];
                    begin1++;
                }
                else
                {
                    temp[j] = arr[begin2];
                    begin2++;
                }
                j++;
            }
            
            while (begin1 <= end1)
            {
                temp[j] = arr[begin1];
                begin1++;
                j++;
            }
            
            while (begin2 <= end2)
            {
                temp[j] = arr[begin2];
                begin2++;
                j++;
            }
            
            //拷貝temp數(shù)組到原數(shù)組（排哪個區(qū)間就拷貝哪個區(qū)間，end2是閉區(qū)間哦）
            for (j=i; j<=end2; j++)
            {
                arr[j] = temp[j];
            }
        }
        gap *= 2;
    }
    
    free(temp);
    temp = NULL;
}

到了這里，關于【排序算法】歸并排序（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！