排序 起泡排序(bubble sort),归并排序(merge sort)

排序 起泡排序(bubble sort),归并排序(merge sort)

1,起泡排序(bubble sort),大致有三种算法

  • 基本版,全扫描。
  • 提前终止版,如果发现前区里没有发生交换,就说明前区已经有序了,直接终止了。但是有个效率低下的地方,就是右边界hi是每次循环向前移动一个单元
  • 跳跃版,在提前终止版的基础上,解决右边界hi移动效率低下的问题。解决思路:每次循环后,记录下最后一次的交换位置A,然后让hi=交换位置A,所以hi就可以跳跃移动多个单元了。

基本版代码实现

//冒泡排序(基本版 效率低下)
template<typename T>
void Vector<T>::bubbleSortA(Rank lo, Rank hi){
  while(lo < hi - 1){
    for(int i = lo; i < hi - 1; ++i){
      if(_elem[i] > _elem[i+1]){
        std::swap(_elem[i], _elem[i+1]);
      }
    }
    hi--;//头不变,不断收缩尾部
  }
}

提前终止版代码实现

//冒泡排序(提前终止版 效率比基础版高)
template<typename T>
void Vector<T>::bubbleSortB(Rank lo, Rank hi){
  while(!bubbleB(lo, hi--));
}
template<typename T>
bool Vector<T>::bubbleB(Rank lo, Rank hi){
  bool sorted = true;//假设整体有序
  for(int i = lo; i < hi - 1; ++i){
    if(_elem[i] > _elem[i+1]){
      sorted = false;
      std::swap(_elem[i], _elem[i+1]);
    }
  }
  return sorted;
}

跳跃版代码实现

//冒泡排序(跳跃版,跳跃移动边界hi 效率最高)
template<typename T>
void Vector<T>::bubbleSortC(Rank lo, Rank hi){
  do{
    hi = bubbleC(lo, hi);
  }while(lo < hi);
}
template<typename T>
Rank Vector<T>::bubbleC(Rank lo, Rank hi){
  Rank last = lo;
  for(int i = lo; i < hi - 1; ++i){
    if(_elem[i] > _elem[i+1]){
      last = i + 1;
      std::swap(_elem[i], _elem[i+1]);
    }
  }
  return last;
}

2,归并排序(merge sort)

利用递归里的减而知之的策略。把数组分为两段,然后分别排序,最后合并在一起。

template <typename T> //向量归并排序
void Vector<T>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
  if ( hi - lo < 2 ) return; //单元素区间自然有序,否则...
  int mi = ( lo + hi ) / 2; //以中点为界
  mergeSort ( lo, mi ); //分别排序
  mergeSort ( mi, hi ); //分别排序
  merge ( lo, mi, hi ); //归并
}
template <typename T> //有序向量(区间)的归并
void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ){ //各自有序的子向量[lo, mi)和[mi, hi)
  T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi)
  int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi)
  for ( Rank i = 0; i < lb; i++ ) B[i] = A[i]; //复制前子向量
  int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi)
  for ( Rank i = 0, j = 0, k = 0; j < lb; ) //归并:反复从B和C首元素中取出更小者
    A[i++] = ( lc <= k || B[j] <= C[k] ) ? B[j++] : C[k++]; //将其归入A中
  delete [] B; //释放临时空间B
}

3,两种排序算法的比较

归并排序的效率高

c/c++ 学习互助QQ群:877684253

排序 起泡排序(bubble sort),归并排序(merge sort)

本人微信:xiaoshitou5854

上一篇:清华邓俊辉数据结构学习笔记(1) - 绪论、向量、列表


下一篇:Monument Tour(以前月赛卡住的签到题,今天突然想起拿出来补一补