归并排序、堆排序与快速排序分析(1)

有段时间没看算法了，今天拿起算法书，随手就翻到排序这一章，排序是几乎每本data structure中都要提到的一部分内容，排序方法可谓林林总总。翻到其中的归并排序和快速排序，由于这两个排序算法都可以用到递归，这里将二者一同列出，进行比较，加深理解。

首先从归并开始

1、归并排序

　　归并排序，从字面上理解，将多个部分进行"归并"在一起，即Merge起来，事实，归并过程中就是对已经有序的部分merge起来的，即两路归并为例，假设需要归并的两个子数组中数据均已经有序，比如，如下的两个子数组。

sub_a[] = {1,3,,5,7}
sub_b[] = {2,4,6,8}

现在需要将两个子数组进行merge，这里可以假设这样的情景：sub_a是一部分扑克牌、sub_b是一部分扑克牌，均按照从小到大，在桌面上反面排列起来，那么merge的过程就是同时翻开最上面的两张牌，比较大小，将小者放到输出中，然后重复上一个操作，其中某一个牌被全部翻完，将另一个剩下的，逐一翻开到输出中即可，从这个角度，很容易理解，merge的时间复杂度是O(n)。

这里因为要check，是否有一列已经翻完，这里为了不用每次判断，某个列是否先翻完所有的牌，可以在每列牌最底部设置一个哨兵，比如设置为最大值0xffffffff,那么每次和最大值比较接口，当翻开的牌数之和达到sizeof(sub_a) + sizeof(sub_b)，那么停止即可，此时，剩下的是两列牌的哨兵，而所有的牌均已经到输出中了，并且已经有序。

这里需要建立buffer来储存输出内容，对应的代码实现如下：

#ifndef NOVA_CTR_INCLUDE/MERGE_SORT_H
#define NOVA_CTR_INCLUDE/MERGE_SORT_H

#include <iostream>

using namespace std;

namespace crafet {

namespace sort {



int merge(int* arr, int p, int q, int r);
int merge_sort(int* arr, int p, int r);

} // end of namespace sort
} // end of namespace crafet

#include "merge_sort.h"

namespace crafet {
namespace sort {


int print_arr(int*arr, int len)
{
    cout << "=====start print array ======" << endl;
    if (NULL == arr) {
        cout << "arr is null" << endl;
    }

    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;

    cout << "=====end print array=====" << endl;

    return 0;
}

int merge(int* arr, int p, int q, int r)
{
    if (NULL == arr) {
        cout << "arr is null" << endl;
    }


    int llen = q - p + 1;
    int rlen = r - q;

//    cout << llen << " " << rlen << endl;
    int llen_sentry = llen + 1;
    int rlen_sentry = rlen + 1;


    int* ltmp = new int[llen_sentry];

    int* rtmp = new int[rlen_sentry];

//    cout << "alloc space succ" << endl;
    memset(ltmp, 0, sizeof(int) * llen_sentry);
    memset(rtmp, 0, sizeof(int) * rlen_sentry);

    int i = 0;
    for( i = 0;i < llen; i++) {
        ltmp[i] = arr[p + i];
    }
    ltmp[i] = 0xffff;
    
    for (i = 0;i < rlen; i++) {
        rtmp[i] = arr[q + 1 + i];
    }
    rtmp[i] = 0xffff;

    print_arr(ltmp, llen_sentry);
    print_arr(rtmp, rlen_sentry);


    int arr_len = llen + rlen;
    int* merged_arr = new int[llen + rlen];

    int total = 0;
    i = 0;
    int j = 0;
    while (total < arr_len) {
        if (ltmp[i] <= rtmp[j]) {
            merged_arr[total] = ltmp[i];
            i++;
        } else {
            merged_arr[total] = rtmp[j];
            j++;
        }

        ++total;
    }

    print_arr(merged_arr, arr_len);
    delete [] ltmp;
    delete [] rtmp;
    delete [] merged_arr;

    return 0;

}

int merge_sort(int*arr, int p, int r)
{
    if(NULL == arr) {
        cout << "arr is null" << endl;
    }

    if (p < r) {
        int q = (p + r)/2;
        merge_sort(arr, p, q);
        cout << "==reverse==" << endl;
        merge_sort(arr, q+1, r);
        merge(arr, p, q, r);
    }

    return 0;
}

} // end of namespace crafet
} // end of namespace sort

2、以大堆为例，先上代码

#include <iostream>
using namespace std;


namespace crafet {
namespace sort {

class CrafetHeapSort {
public:

    CrafetHeapSort();
    virtual ~CrafetHeapSort();

public:

    int init();

    int set_arr_len(int arr_len);
    /**
     * @brief load data into array
     */
    int load_data(int* given_arr, int arr_len);

    /**
     * @brief adjust parent node to build local max heap
     * @return 0 succ, others -1
     */
    int adjust_max_heap(int parent);

    /**
     * @brief build a max heap given array
     */
    int build_max_heap();

    /**
     * @brief max heap sort for array
     */
    int max_heap_sort();
private:

    int arr_swap(int left, int right);

    int print_heap_arr();
private:

    int* _heap_arr;
    int _arr_len;
    

};

} // end of namespace sort
} // end of namespace crafet

#include "heap_sort.h"

namespace crafet {
namespace sort {

CrafetHeapSort::CrafetHeapSort()
{
}

CrafetHeapSort::~CrafetHeapSort()
{
}

int CrafetHeapSort::init()
{
    _heap_arr = NULL;
    _arr_len = 1;
}

int CrafetHeapSort::set_arr_len(int arr_len)
{
    _arr_len = arr_len;
}

int CrafetHeapSort::load_data(int* given_arr, int arr_len)
{
    if (NULL == given_arr) {
        cout << "given_arr is null" << endl;
    }

    _heap_arr = new int[arr_len];

    memset(_heap_arr, 0, sizeof(int) * arr_len);

    for (int i = 0; i < arr_len; i++) {
        *(_heap_arr + i) = given_arr[i];
    }

    set_arr_len(arr_len);

    print_heap_arr();

    return 0;
}

int CrafetHeapSort::adjust_max_heap(int parent)
{   
    if (NULL == _heap_arr) {
        cout << "arr is null" << endl;
        return -1;
    }

    if (parent >= _arr_len) {
        cout << "index [" << parent << "] exceed bound" << endl;
        return -1;
    }

    int largest = parent;
    
    int left = (parent << 1) + 1;
    int right = (parent << 1) + 2;

    cout << "left " << left << " right " << right << endl; 
    int key = _heap_arr[parent];
    if (left < _arr_len && _heap_arr[left] > key) {
        largest = left;
    }

    if (right < _arr_len && _heap_arr[right] > _heap_arr[largest]) {
        largest = right;
    }

    cout << "largest " << largest << endl;
    //two if above tiggered
    if (largest != parent) {
        arr_swap(parent, largest);
        
        print_heap_arr();
        //adjust changed child node
        adjust_max_heap(largest);

    }

    return 0;
}

int CrafetHeapSort::arr_swap(int left, int right)
{
    if (left >= _arr_len || right >= _arr_len) {
        cout << "index exceed" << endl;
        return -1;
    }

    int tmp = 0;
    tmp = _heap_arr[left];
    _heap_arr[right] = _heap_arr[left];
    tmp = _heap_arr[right];

    return 0;
}

int CrafetHeapSort::print_heap_arr()
{
    cout << "===== start to print heap =====" << endl;
    for (int i = 0; i < _arr_len ; i++) {
        cout << _heap_arr[i] << " ";
    }

    cout << endl;

    cout << "===== end to print heap =====" << endl;
    return 0;
}


} // end of namespace sort
} // end of namespace crafet

在编码过程中遇到一个bug，

在最初的编码为：

    //two if above tiggered
    if (largest != parent) {
        arr_swap(parent, largest);
    
    }   
        
    print_heap_arr();
    //adjust changed child node
    adjust_max_heap(largest);

明显，当父节点与子节点并没有交换的时候，即可以正常退出的时候，还要继续进行尾递归，结果造成死循环，所以

需要尾递归的前提是，有节点发生交换。

即应该是

    //two if above tiggered
    if (largest != parent) {
        arr_swap(parent, largest);
        
        print_heap_arr();
        //adjust changed child node
        adjust_max_heap(largest);

    }

同时发现，largest成员变量的初始化也有微妙的trick，

最初初始化形式为：

int largest = 0;

这里会带来一次多余的比较，即当parent并没有任何子节点进行swap的时候，此时largest=0，这样largest != parent 就会成立，

因为会发生一次，与堆顶元素的交换，这次交换明显是不对的。

因此，调整largest的初始化形式：

int largest = parent;

这样，当父节点与子节点无任何swap的时候， largest仍然等于parent，此时不满足再次递归的条件，从而正确退出。

给定如下的测试用例：

#include "heap_sort.h"

using namespace crafet::sort;

int main()
{
    int arr[] = {12, 3, 6, 8, 21, 24, 17, 9, 2};

    CrafetHeapSort chs;

    chs.init();

    int arr_len = 9;
    chs.load_data(arr, 9);

    chs.adjust_max_heap(3);
}

这里为了测试，许多地方编码没有考虑更多的扩展，如：用构造的数组来初始化堆数组，更有扩展性的设计应该是数据放入文件，load即可，这不是当前的重点，因此仅仅给出测试用例。

当前的堆排序，仅仅实现到对某一个节点进行调整形成局部的最大堆，后面会继续基于此进行扩展，建立完成的最大堆，同时，实现堆排序。