萬盛學電腦網

 萬盛學電腦網 >> 網絡編程 >> 編程語言綜合 >> 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結果一樣, 基本說明這個代碼是正確的。

copyright © 萬盛學電腦網 all rights reserved