上一篇C++基礎(chǔ)入門(mén)之模板堆排序(上):模板上的list的創(chuàng)造與操作
其實(shí)接下來(lái)就很簡(jiǎn)單了淮逻，只要把大眾版的堆排序翻譯過(guò)來(lái)就行了
三. 生造heapSort
一樣是四大函數(shù) (這個(gè)接口搞得有點(diǎn)亂琼懊，將就看一下
- swap
- maxHeapify
- build
- sort
swap很簡(jiǎn)單，沒(méi)什么可說(shuō)的爬早，一個(gè)swap相當(dāng)于兩次change_list
template<int a, int b, class _list>
struct swap {
using temp = typename change_list<a, find_list<b, _list>::result::value, _list>::result;
using result = typename change_list<b, find_list<a, _list>::result::value, temp>::result;
};
有了swap應(yīng)該可以寫(xiě)冒泡排序了
先把簡(jiǎn)單的放上來(lái)哼丈，build函數(shù)，里面生造了一個(gè)loop循環(huán)筛严，從i循環(huán)到0醉旦；
因?yàn)樽兞坎豢勺儯杂涀oop也是要有l(wèi)ist這個(gè)參數(shù)的
template<class _list, int heapSize>
struct build {
template<int i, class _list>
struct loop {
using result = typename loop<i - 1, typename maxHeapify<_list, i, heapSize>::result>::result;
};
template<class _list>
struct loop<0, _list> {
using result = typename maxHeapify<_list, 0, heapSize>::result;
};
using result = typename loop<(heapSize / 2), _list>::result;
};
sort也一樣簡(jiǎn)單桨啃，沒(méi)什么好說(shuō)的……留下temp的中間過(guò)程會(huì)比較容易讀懂车胡。
template<class _list, int heapSize>
struct sort {
using temp = typename build<_list, heapSize>::result;
template<int i, class _list>
struct loop {
using temp = typename swap<0, i, _list>::result;
using temp2 = typename maxHeapify<temp, 0, i>::result;
using result = typename loop<i - 1, temp2>::result;
};
template<class _list>
struct loop<1, _list> {
using temp = typename swap<0, 1, _list>::result;
using result = typename maxHeapify<temp, 0, 1>::result;
};
using result = typename loop<(heapSize - 1), _list>::result;
};
最復(fù)雜的是這個(gè)東西， 對(duì)比一下大眾版的堆排序
void maxHeapify(T arr[], int index, int heapSize) {
int maxIndex = index;
int left = 2 * index + 1;
int right = left + 1;
if (left < heapSize && arr[index] < arr[left]) {
maxIndex = left;
}
if (right < heapSize && arr[maxIndex] < arr[right]) {
maxIndex = right;
}
if (maxIndex != index) {
swap(arr[maxIndex], arr[index]);
maxHeapify(arr, maxIndex, heapSize);
}
return;
}
其中這個(gè)
if (left < heapSize && arr[index] < arr[left]) {
····maxIndex = left;
}
if (right < heapSize && arr[maxIndex] < arr[right]) {
····maxIndex = right;
}
我發(fā)現(xiàn)如果去做個(gè)通常版本的if_then_else像這樣不一定能用照瘾，訪(fǎng)問(wèn)仍有會(huì)過(guò)界的匈棘，所以只好把結(jié)果都丟到元函數(shù)類(lèi)中的元函數(shù)類(lèi)了
template<bool Cond, class Then, class Else>
struct If{using result = Then;};
template<bool Cond, class Then, class Else>
struct If<false>{using result = Else;};
以上并不那么好用，所以還是根據(jù)實(shí)際情況生造了一個(gè)并且把if判斷做成嵌套
if (left < heapSize) {
····if(arr[index] < arr[left])
········maxIndex = left;
····else
········maxIndex = index;
}
else
····maxIndex = index;
（現(xiàn)在我已經(jīng)不想看它了……好復(fù)雜
template<class _list, int index, int heapSize>
struct maxHeapify {
static const int left = 2 * index + 1;
static const int right = left + 1;
template<bool cond, int index, int num1>
struct if_temp {
static const int max = index;
};
template<int index, int num1>
struct if_temp<true, index, num1> {
template<bool cond, int index, int num1>
struct if_temp2 {
static const int max = index;
};
template<int index, int num1>
struct if_temp2<true, index, num1> {
static const int max = num1;
};
static const int max = if_temp2 < ((find_list<index, _list>::result::value) < (find_list<num1, _list>::result::value)), index, num1>::max;
};
static const int temp_max = if_temp<(left < heapSize), index, left>::max;
static const int maxIndex = if_temp<(right < heapSize), temp_max, right>::max;
template<bool cond1, int maxIndex, int index, int heapSize>
struct if_temp3 {};
template<int maxIndex, int index, int heapSize>
struct if_temp3<false, maxIndex, index, heapSize> {
using result = _list;
};
template<int maxIndex, int index, int heapSize>
struct if_temp3<true, maxIndex, index, heapSize> {
using temp_list = typename swap<maxIndex, index, _list>::result;
using result = typename maxHeapify<temp_list, maxIndex, heapSize>::result;
};
using result = typename if_temp3<(maxIndex != index), maxIndex, index, heapSize>::result;
};
