排序 起泡排序(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，两种排序算法的比较
归并排序的效率高