歸並排序算法的理解

歸並排序算法的理解

歸並排序：先對兩個有序的系列進行合並，合並的時候不斷的對兩個系列的第一個元素進行比較，把較小的那個移動到最前面成為了第一個元素，那麼移動的元素後面的元素就是成為了下次比較的序列的第一個元素，如此不斷的取兩個系列的第一個元素進行比較。

1 4 5 6 2 7 8 9 第一輪1與2比較 1比2小， 那麼1被移動了 4成為了下次要比較的元素了

那麼下一輪就是比較4和2 2小就被移動了 那麼再次比較的就是4和7了 如此一輪一輪的比較。

//merge two array：對兩個有序列進行合並
void merge(int a[], int temp[], int first, int mid, int end)
{
	int i = first, j = mid + 1;
	int m = mid, n = end;
	int k = 0;

	while (i <= m && j <= n)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}

	while (i <= m)
		temp[k++] = a[i++];
	while (j <= n)
		temp[k++] = a[j++];

	for (int i = 0; i < k; i++)/*把存儲在臨時對象temp中排好序列copy到a中對應的下標上*/
		a[first + i] = temp[i];
}

上面只是對兩個有序的系列進行合並，還沒有對序列進行排序，那麼如何排序了，這裡我們要用到遞歸的思想，就是把序列分成若干個系列再合並，分裂到最後必然小的系列，包含一個元素，一個元素的系列必然是有序的， 然後逆向合並，合並起來的必然是有序的。

void merge_sort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		merge_sort(a, first, mid, temp);    //it's let letf have a regular
		merge_sort(a, mid + 1, last, temp); //it's let right have a regular
		merge(a, temp, first, mid, last); //merge two  in  one  
	}
}

寫個測試代碼：

int main()
{
	int a[] = { 1, 8, 6, 7, 9, 45, 68, 100, 5 };

	int k = (sizeof(a) / sizeof(int));

	int *p = new int[k];

	merge_sort(a,0,k-1,p);

	for (int i = 0; i < k; i++)
		cout << a[i] << " ";

	return 0;
}