排序(6)

歸並排序：

歸並操作,也叫歸並算法，指的是將兩個已經排序的序列合並成一個序列的操作。歸並排序算法依賴歸並操作。

歸並操作的過程如下：
(1) 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
(2) 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
(3) 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
(4) 重復步驟3直到某一指針到達序列尾

(5) 將另一序列剩下的所有元素直接復制(抄)到合並序列尾

簡單的說，就是將一個序列不斷的進行二分（當然也可以三分、多分）分裂，然後遞歸下去，再合並。

源代碼：

/*=============================================================================
#
#     FileName: Merge_Sort.c
#         Desc: 歸並排序
#
#       Author: zhangyuqing   
#
#      Created: 2014年6月29日23:18:16
#      Version: 0.0.1
#
=============================================================================*/


#include "stdafx.h"
#include 
#include 


//歸並操作
void merge(int src[], int des[], int low, int high ,int mid)
{
	int i = low;
	int k = low;
	int j = mid + 1;

	while (( i <= mid ) && ( j <= high ))
	{
		if (src[i] < src[j])
		{
			des[k++] = src[i++];
		}
		else
		{
			des[k++] = src[j++];
		}		
	}
	while (i <= mid)
	{
		des[k++] = src[i++];
	}
	while (j <= high)
	{
		des[k++] = src[j++];
	}
}

void MSort(int src[], int des[] ,int low, int high, int max_size)
{
	int mid = (low + high) / 2;
	if (low == high)
	{
		des[low] = src[low];
	}
	else
	{
		int mid = (low + high) / 2;
		int * des_space = (int *)malloc(sizeof(int) * max_size);

		if (NULL != des_space)
		{
			MSort( src, des_space, low, mid, max_size);
			MSort( src, des_space, mid+1, high, max_size);

			merge( des_space, des, low, high, mid);
		}	

		free(des_space);
	}
}

void Meger_Sort(int arr[], int low, int high, int len)
{
	MSort( arr, arr, low, high, len);
}

int main(void)
{
	int arr[10];
	
	for ( int i=0; i<10; i++)  //初始化數據
	{
		arr[i] = rand()%100;  //隨機生成數據
	}
	printf("Before sort:\n");  //打印排序前的數據
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);
	}

	//開始排序
	Meger_Sort( arr, 0, 10-1, 10);


	printf("\nAfter sort:\n"); //打印排序後的數據
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);
	}
	system("pause");
	return 0;
}

運行結果：

Before sort:
41 67 34 0 69 24 78 58 62 64
After sort:
0 24 34 41 58 62 64 67 69 78 請按任意鍵繼續. . .

如有錯誤，望不吝指出。