C++基础入门之模板堆排序(下):堆排序——简单的翻译

上一篇C++基础入门之模板堆排序(上):模板上的list的创造与操作

其实接下来就很简单了，只要把大众版的堆排序翻译过来就行了

三. 生造heapSort

一样是四大函数 (这个接口搞得有点乱，将就看一下

• swap
• maxHeapify
• build
• sort

swap很简单，没什么可说的，一个swap相当于两次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应该可以写冒泡排序了

先把简单的放上来，build函数，里面生造了一个loop循环，从i循环到0；
因为变量不可变，所以记住loop也是要有list这个参数的

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也一样简单，没什么好说的……留下temp的中间过程会比较容易读懂。

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;
};

最复杂的是这个东西， 对比一下大众版的堆排序

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;
}

其中这个
if (left < heapSize && arr[index] < arr[left]) {
····maxIndex = left;
}
if (right < heapSize && arr[maxIndex] < arr[right]) {
····maxIndex = right;
}
我发现如果去做个通常版本的if_then_else像这样不一定能用，访问仍有会过界的，所以只好把结果都丢到元函数类中的元函数类了

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;};

以上并不那么好用，所以还是根据实际情况生造了一个并且把if判断做成嵌套
if (left < heapSize) {
····if(arr[index] < arr[left])
········maxIndex = left;
····else
········maxIndex = index;
}
else
····maxIndex = index;

（现在我已经不想看它了……好复杂

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;
};