程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++ 歸並排序實現(算法導論)

C++ 歸並排序實現(算法導論)

編輯:C++入門知識

算法導論上的下標是從1開始的,但是為了和c++ STL的設計思想一致,所有函數的實現統一用左閉右開區間.中間修改了很多次,因為下標修改不是很容易就改掉的,需要始終維持循環不變式,稍微一個步驟出錯就會使結果有些錯誤。

#include 
#include 
#include 
#include 
using namespace std;
void merge(int *A, int p, int q, int r) {      //merge [p, r),左閉右開區間
	int n1 = q - p, n2 = r - q;                //注意數量的變化與書上的不同,使用左閉右開區間的優勢就是統一數量的形式表示
	int *L = new int[n1], *R = new int[n2];
	for (int i = 0; i < n1; ++i)              //L[0, n1)  <==    A[p, q)
		L[i] = A[p+i];              
	for (int i = 0; i < n2; ++i)              //R[0, n2)  <==    A[q, r)
		R[i] = A[q+i];                   //此處不是q+i+1
	int i = 0, j = 0;
	int k = p;
	while (i < n1 && j < n2) {               
		if (L[i] <= R[j])
			A[k++] = L[i++];
		else
			A[k++] = R[j++];
	}
	while (i < n1)                           //由於沒有了哨兵,需要添加多余元素
		A[k++] = L[i++];
	while (j < n2)
		A[k++] = R[j++];
	delete [] L;
	delete [] R;
}
void merge_sort(int *a, int p, int r) {    //調用接口 merge_sort(a, 0, len), 不是(a, 0, len-1)了
	if (p < r - 1) {                       //此時不是p < r了,左閉右開區間當p>=r-1時子數組最多一個元素
		int q = p + (r - p)/2;
		merge_sort(a, p, q);
		merge_sort(a, q, r);           //注意接口統一了,這個不是(a, q+1, r)而是(a, q, r)了,左閉右開的好處
		merge(a, p, q, r);
	}
}
int main()
{
	srand(time(NULL));
	int n;
	while (cin >> n) {
		int a[n];
		for (int i = 0; i < n; ++i)
			a[i] = rand() % n;
		for (int i = 0; i < n; ++i)
			printf("%d ", a[i]);
		printf("\n");
		merge_sort(a, 0, n);
		for (int i = 0; i < n; ++i)
			printf("%d ", a[i]);
		printf("\n");
	}
}

最後用了幾萬組測試數據,得出的結果均與stl裡的sort結果一樣, 基本說明這個代碼是正確的。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved