大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 常用排序算法——归并排序法

常用排序算法——归并排序法


[摘要]本文主要是对常用排序算法——归并排序法的讲解,希望对大家学习常用排序算法——归并排序法有所帮助。

  归并排序采用的是分治思想,将数组不断分解为子数组,直到子数组只有一个元素,每次分解对应一个归并函数,归并函数可以将当前分解的两个子数组合并起来。有两种方式可以实现归并排序,第一种是递归方式实现的,代码如下:

  #include <IOSTREAM>

  static void merge( int* array, int* tmp, size_t start, size_t end){

  size_t i = start, j = (start+end)/2, pos = start;

  while(i != (start+end)/2 && j != end){

  if(array[i] < array[j]){

  tmp[pos++] = array[i++];

  }

  else{

  tmp[pos++] = array[j++];

  }

  }

  for(;i != (start+end)/2; ++i){

  tmp[pos++] = array[i];

  }

  for(;j != end; ++j){

  tmp[pos++] = array[j];

  }

  for(i = start; i != end; ++i){

  array[i] = tmp[i];

  }

  }

  static void merge_sort_service (int * array, int* tmp, size_t start, size_t end){

  if(end-start > 2){

  merge_sort_service(array, tmp, start, (start+end)/2);

  merge_sort_service(array, tmp, (start+end)/2, end);

  }

  merge(array, tmp, start, end);

  }

  void merge_sort( int* array, size_t len){

  int* pArray = new int[len];

  merge_sort_service(array, pArray, 0, len);

  delete [] pArray;

  }

  int main(){

  int array[10] = {3, 9, 5, 1, 8, 7, 2, 4, 6, 0};

  merge_sort(array, 10);

  for(int i = 0; i != 10; ++i){

  std::cout 《 array[i] 《 " ";

  }

  std::cout 《 std:: endl;

  return 0;

  }

 

  第二种是基于循环的非递归方式实现的,整体性能要高于递归方式实现的归并排序,代码如下:

  #include <IOSTREAM>

  void merge( int* array, int* tmp, size_t length, size_t step){

  size_t i, j, pos, i_stop, j_stop;

  size_t k = 0;

  size_t stop = length-step;

  while(k < stop){

  pos = k;

  i_stop = k+step-1;

  j_stop = (k+2*step)<(length)?(k+2*step-1):(length-1);

  for(i = k, j = k+step; i <= i_stop && j <= j_stop; ){

  if(array[i] < array[j]){

  tmp[pos++] = array[i++];

  }

  else{

  tmp[pos++] = array[j++];

  }

  }

  while(i <= i_stop){

  tmp[pos++] = array[i++];

  }

  while(j <= j_stop){

  tmp[pos++] = array[j++];

  }

  k += 2*step;

  }

  for(i = 0; i != length; ++i){

  array[i] = tmp[i];

  }

  }

  void merge_sort( int* array, size_t length ){

  int* tmp = new int[length ];

  size_t k = 1;

  while(k < length){

  merge(array, tmp, 10, k);

  k *= 2;

  }

  delete [] tmp;

  }

  int main(){

  int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

  merge_sort(array, 10);

  for(int i = 0; i != 10; ++i){

  std::cout 《 array[i] 《 " ";

  }

  std::cout 《 std:: endl;

  return 0;

  }

  由于后一种方法使用的是循环而非递归,减少了函数调用及堆栈开销,效率上高于第一种,但编写起来比第一种实现方式麻烦。


相关Java技巧推荐

    暂时没有相关推荐



    相关评论