歸并排序算法(mergesort)是將一個序列劃分為同樣大小的兩個子序列,然后對兩個子序列分別進(jìn)行排序,最后進(jìn)行合并操作,將兩個子序列合成有序的序列.在合成的過程中,一般的實現(xiàn)都需要開辟一塊與原序列大小相同的空間,以進(jìn)行合并操作,歸并排序算法的示例在
這里.
這里介紹一種不需要開辟新的空間就可以進(jìn)行歸并操作的算法.算法的核心部分是以下代碼:
1 /**
2 * 算法: 合并二已排序的連續(xù)序列
3 **/
4 template<typename T>
5 void t_merge( T& v, size_t size, size_t pos )
6 {
7 size_t fir = 0, sec = pos;
8 while ( fir < sec && sec < size )
9 {
10 while ( fir < sec && v[fir] <= v[sec] ) fir++;
11 size_t maxMove = 0;
12 while ( sec < size && v[fir] > v[sec] ) maxMove++, sec++;
13 t_exchange( &v[fir], sec - fir, sec - fir - maxMove );
14 fir += maxMove;
15 }
16 }
其中T是一個數(shù)組, size是數(shù)組尺寸, pos是歸并劃分的位置.也就是說[0,pos)和[pos, size)都分別是有序的.比如對序列1, 3, 5, 7, 2, 4, 6, 8進(jìn)行歸并操作, 此時size=8, pos = 4.
以<<算法導(dǎo)論>>中介紹的通過循環(huán)不變量的方法證明算法的正確性,在這個算法中, 循環(huán)不變量為[fir, sec)中的元素都是有序的:
1) 初始:此時fir = 0, sec = pos, 以前面介紹的函數(shù)參數(shù)的說明來看,滿足循環(huán)不變量.
2) 迭代:來看看循環(huán)做了些什么操作.行10進(jìn)行的操作為, 只要滿足fir元素不大于sec元素, fir就一直遞增;行12進(jìn)行的操作是只要滿足fir大于sec, sec就一直遞增, 同時遞增maxMove計數(shù).因此, 進(jìn)行完前面兩個步驟之后, fir所指元素一定小于sec以及其后的所有元素.而位于sec之前的第二個子序列中的元素, 一定小于fir.因此, [sec-maxMove, sec)z中的元素小于所有[fir, sec - 1)的元素.通過調(diào)用
t_exchange函數(shù)將位于[sec-maxMove, sec)中的元素"旋轉(zhuǎn)"到fir之前.
也就是說, 這個過程在第二個已經(jīng)排序好的子序列中尋找在它之內(nèi)的小于目前第一個已經(jīng)排序好的子序列的序列, 將它"旋轉(zhuǎn)"到前面.
以序列
1, 3, 5, 7, 2, 4, 6, 8為例, 此時fir=1也就是指向3, sec=5也就是指向4, maxMove=1, 通過調(diào)用t_exchange函數(shù)之后將[sec-maxMove, sec)即[4,5)中的元素也就是2"旋轉(zhuǎn)"到子序列3,5,7之前,于是該循環(huán)結(jié)束之后序列變?yōu)?,2,3,5,7,4,6,8, 此時fir=2, sec =5, 滿足循環(huán)不變量.
3) 終止: 當(dāng)循環(huán)終止時, fir或者sec之一超過了數(shù)組的尺寸, 顯而易見, 此時序列變成了有序的.
完整的算法如下所示, 需要特別說明的是, 這段代碼不是我想出來的, 原作者在
這里:
#include <stdio.h>
#include <iostream>
using namespace std;
//int array[] = {1, 3, 5, 7, 2, 4, 6, 8};
int array[] = {3,5,7,8,1,2,4,6};
void display(int array[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d ", array[i]);
}
printf("\n");
}
/**
* 算法: 交換二對象
**/
template<typename T>
void t_swap( T& v1, T& v2 )
{
T t = v1; v1 = v2; v2 = t;
}
/**
* 算法: 反轉(zhuǎn)序列
**/
template<typename T>
void t_reverse( T* v, size_t size )
{
size_t s = 0, e = size-1;
while( s < e && s < size && e > 0 )
t_swap( v[s++], v[e--] );
}
/**
* 算法: 手搖算法,從指定位置旋轉(zhuǎn)序列(見編程珠璣第二章)
**/
template<typename T>
void t_exchange( T* v, size_t size, size_t n )
{
t_reverse( v, n );
t_reverse( v + n, size - n );
t_reverse( v, size );
}
/**
* 算法: 合并二已排序的連續(xù)序列
**/
template<typename T>
void t_merge( T& v, size_t size, size_t pos )
{
size_t fir = 0, sec = pos;
while ( fir < sec && sec < size )
{
while ( fir < sec && v[fir] <= v[sec] ) fir++;
size_t maxMove = 0;
while ( sec < size && v[fir] > v[sec] ) maxMove++, sec++;
t_exchange( &v[fir], sec - fir, sec - fir - maxMove );
fir += maxMove;
display(array, sizeof(array)/sizeof(int));
}
}
/**
* 算法: 歸并排序
**/
template<typename T>
void t_merge_sort( T* v, size_t size )
{
if ( size <= 1 ) return;
t_merge_sort( v, size/2 );
t_merge_sort( v + size/2, size - size/2 );
t_merge( v, size, size/2 );
}
int main()
{
display(array, sizeof(array)/sizeof(int));
t_merge(array, sizeof(array) / sizeof(int), (sizeof(array)/sizeof(int))/2);
//t_merge_sort(array, sizeof(array) / sizeof(int));
display(array, sizeof(array)/sizeof(int));
return 0;
}
補(bǔ)充說明:
其實前面采用"旋轉(zhuǎn)"算法將元素前移不是必須的, 可以將所要移動的元素之前的部分后移, 再將元素插入到合適的位置.比如前面說的對于序列1, 3, 5, 7, 2, 4, 6, 8, 第一步要將元素2前移至3之前, 可以將3,5,7后移, 然后將2插入到合適的位置.
但是這樣有一個問題, 如果要移動的元素多了, 那么就需要更多的臨時空間保存要前移的元素, 這樣對空間就不是O(1)的了.而旋轉(zhuǎn)算法可以做到O(1)的空間達(dá)到要求.