NO IMAGE

一、簡介

    雙調排序(Bitonic Sort)屬於排序網路(Sorting Network)的一種,它是一種可以平行計算的排序演算法。

    要理解雙調排序,首先需要理解雙調序列,雙調序列定義如下:

    如果序列<a0, a1, …, an-1>滿足以下兩個條件之一,則稱之為雙調序列:™

    存在一個0≤k≤n-1,使得<a0, a1, …, ak-1>為升序序列,<ak, ak 1, …, an-1>為降序序列;或存在一個標號的迴圈移位,使得條件1)滿足。

    如果n為偶數,且<a0, a1, …, an/2-1>為升序序列,<an/2, an/2 1, …, an-1>為降序序列,則以下兩個序列都是雙調序列

    S1=<min(a0, an/2), min(a1, an/2 1), …, min(an/2-1, an-1)>

    S2=<max(a0, an/2), max(a1, an/2 1), …, max(an/2-1, an-1)>

    雙調排序主要思想:

    1、首先不斷的二分,直到每組只剩下一個元素,然後開始歸併。

    2、雙調排序歸併時以不大於n的最大2的冪次方2^k為界限,把2^k~n的元素分別與0~(n-2^k)的元素比較,然後再分別在0~2^k和2^k~n這兩段上應用比較網路。

    3、雙調排序難以理解的地方就在於這個歸併的過程,假設我們要把長度為n的序列a升序排列,由於二分時是把前n/2的序列降序排列後n/2的序列升序排列的,而n-2^k < n/2,所以前n-2^k 和後n-2^k個元素都大於中間的元素,當前n-2^k個元素和後n-2^k個元素比較時,會把序列中最大的n-2^k個元素放到最後n-2^k個位置上,也就是說比較後,2^k~n的元素都比0~2^k的元素大,這樣在分別對這兩段用同樣的方法歸併,最終得到完整的升序序列。

    以6個元素的序列為例,當前3個元素已經降序排好,後3個元素已經升序排好(遞迴到底時是從1個元素開始返回的,所以對6個元素歸併時前後3個元素已經排好序),這個以4(不大於6的最大2的冪次方)為界限,分別讓第1個和第5個、第2個和第6個元素比較,使得這6個元素中最大的兩個處於第5、6個位置上,然後再分別對前4個和後2個元素按此方法歸併,最終遞迴完成排序。

二、演算法實現

//雙調歸併過程
template <typename T>
void BitonicMerge(T* pFirst,T* pLast,bool bDirection)
{
T* pTemp = pFirst;
if(pFirst < pLast)
{
int nLength = pLast - pFirst   1;                   //計算陣列長度
int nMid = 1;
while(nMid < nLength)                               //計算小於陣列長度的2的最大冪次方值k
nMid = nMid << 1;
nMid = nMid >> 1;
for(int i=0;i< nLength - nMid;i  )                  //對元素0~n-k和元素k~n進行比較,根據升序降序標誌bDirection對元素進行交換
{
if((*(pTemp i) > *(pTemp i nMid)) == bDirection)
{
Swap(*(pTemp i),*(pTemp i nMid));
}
}
BitonicMerge(pFirst,pFirst nMid-1,bDirection);      //遞迴對陣列前後兩部分元素進行雙調遞迴
BitonicMerge(pFirst nMid,pLast,bDirection);
}
}
//Bitonic排序(雙調排序):屬於排序網路(Sorting Network)的一種,它是一種可以平行計算的排序演算法。
//首先,雙調序列是指序列要麼先單調遞增然後再單調遞減,要麼先單調遞減然後又單調遞增。
//通過對要排序的陣列構造雙調序列,然後遞迴進行雙調歸併即可完成對陣列的排序
template <typename T>
bool BitonicSort(T* pFirst,T* pLast,bool bDirection,Compare pFun)
{
bool bIsReverse = false;
T* pTemp = NULL;
if((pFirst == NULL) || (pLast == NULL))
{
cout<<"Input parameters error!"<<endl;
return false;
}
if(pFirst > pLast)
{
bIsReverse = true;
pTemp = pFirst;
pFirst = pLast;
pLast = pTemp;
}
if(pFirst < pLast)
{
int nNum = pLast - pFirst   1;                         //計算陣列長度
int nMid = nNum / 2;                                   //計算中間元素索引值
BitonicSort(pFirst,pFirst nMid-1,!bDirection);         //對陣列前半部分遞迴進行分裂
BitonicSort(pFirst nMid,pLast,bDirection);             //對陣列後半部分遞迴進行分裂
BitonicMerge(pFirst,pLast,bDirection);                 //雙調歸併過程
}
if(bIsReverse)
{
while(pFirst < pLast)
{
Swap(*pFirst,*pLast);
pFirst;
--pLast;
}
}
return true;
}

    其他排序演算法及資料結構的具體實現詳見GitHub:https://github.com/daiyl0320/IntroductionToAlgorithms