歸并排序算法(mergesort)是將一個序列劃分為同樣大小的兩個子序列,然后對兩個子序列分別進行排序,最后進行合并操作,將兩個子序列合成有序的序列.在合成的過程中,一般的實現都需要開辟一塊與原序列大小相同的空間,以進行合并操作,歸并排序算法的示例在
這里.
這里介紹一種不需要開辟新的空間就可以進行歸并操作的算法.算法的核心部分是以下代碼:
1 /**
2 * 算法: 合并二已排序的連續序列
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是一個數組, size是數組尺寸, pos是歸并劃分的位置.也就是說[0,pos)和[pos, size)都分別是有序的.比如對序列1, 3, 5, 7, 2, 4, 6, 8進行歸并操作, 此時size=8, pos = 4.
以<<算法導論>>中介紹的通過循環不變量的方法證明算法的正確性,在這個算法中, 循環不變量為[fir, sec)中的元素都是有序的:
1) 初始:此時fir = 0, sec = pos, 以前面介紹的函數參數的說明來看,滿足循環不變量.
2) 迭代:來看看循環做了些什么操作.行10進行的操作為, 只要滿足fir元素不大于sec元素, fir就一直遞增;行12進行的操作是只要滿足fir大于sec, sec就一直遞增, 同時遞增maxMove計數.因此, 進行完前面兩個步驟之后, fir所指元素一定小于sec以及其后的所有元素.而位于sec之前的第二個子序列中的元素, 一定小于fir.因此, [sec-maxMove, sec)z中的元素小于所有[fir, sec - 1)的元素.通過調用
t_exchange函數將位于[sec-maxMove, sec)中的元素"旋轉"到fir之前.
也就是說, 這個過程在第二個已經排序好的子序列中尋找在它之內的小于目前第一個已經排序好的子序列的序列, 將它"旋轉"到前面.
以序列
1, 3, 5, 7, 2, 4, 6, 8為例, 此時fir=1也就是指向3, sec=5也就是指向4, maxMove=1, 通過調用t_exchange函數之后將[sec-maxMove, sec)即[4,5)中的元素也就是2"旋轉"到子序列3,5,7之前,于是該循環結束之后序列變為1,2,3,5,7,4,6,8, 此時fir=2, sec =5, 滿足循環不變量.
3) 終止: 當循環終止時, fir或者sec之一超過了數組的尺寸, 顯而易見, 此時序列變成了有序的.
完整的算法如下所示, 需要特別說明的是, 這段代碼不是我想出來的, 原作者在
這里:
#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;
}
/**
* 算法: 反轉序列
**/
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--] );
}
/**
* 算法: 手搖算法,從指定位置旋轉序列(見編程珠璣第二章)
**/
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 );
}
/**
* 算法: 合并二已排序的連續序列
**/
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;
}
補充說明:
其實前面采用"旋轉"算法將元素前移不是必須的, 可以將所要移動的元素之前的部分后移, 再將元素插入到合適的位置.比如前面說的對于序列1, 3, 5, 7, 2, 4, 6, 8, 第一步要將元素2前移至3之前, 可以將3,5,7后移, 然后將2插入到合適的位置.
但是這樣有一個問題, 如果要移動的元素多了, 那么就需要更多的臨時空間保存要前移的元素, 這樣對空間就不是O(1)的了.而旋轉算法可以做到O(1)的空間達到要求.