第50课 堆排序和桶排序

1. 堆排序（Heap Sort）

（1）堆：这里所指的堆，一般是一颗完全二叉树，同时满足以下两个性质（以大顶堆为例）

 

　　①每个父结点的键值总是大于等于其左右孩子的键值。

　　②每个结点的左子树和右子树都是一个大顶堆。

（2）基本思想（以大顶堆为例）：

 

　　将待排序的序列构成一个大顶堆（如图①）。此时，整个序列的最大值就是堆顶的根结点。并将它与堆数组的堆末尾元素交换，在堆末尾形成有序区(最大值)（如图②）。然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值（如图③）。如此反复执行，便能得到一个有序序列。

（3）实例分析

 

2. 桶排序

（1）基本思想：将要排列的序列分成n组，每组分别进行排序，然后在合并到一起，这里面有分而治之的思想。

 

（2）基本流程：

　　①建立一定数量的桶（buckets）；

　　②遍历原始数组，并按一定的算法将数据放入到各自的buckets中(类似于哈希函数)；

　　③对非空的buckets进行排序；（可能使用别的排序算法）

　　④按照顺序遍历这些buckets并放回到原始数组中即可构成排序后的数组。

（3）实例分析

 

【编程实验】堆排序（HeapSort）和桶排序算法（BucketSort）

//Sort.h

#ifndef SORT_H
#define SORT_H

#include "Object.h"

namespace DTLib
{

//结点（for BucketSort）
template <typename T>
class BNode : public Object
{
public:
    T data;
    BNode<T>* next;
public:
    BNode(){next = NULL;}
};

class Sort : public Object
{  
private:
    //私有化构造函数、赋值、拷贝构造等函数
    Sort();
    Sort(const Sort&);
    Sort& operator=(const Sort&);

    template <typename T>
    static void Swap(T& a, T& b)
    {
        T temp(a);
        a = b;
        b = temp;
    }

    //两路合并算法中的合并过程
    template <typename T> //将两个有序序列array[low...mid]和array[mid+1...high]
    static void Merge(T src[], T helper[], int low, int mid, int high, bool min2max)
    {
        int i = low;
        int j = mid +1;
        int k = 0;

        //按顺序将两个有序序列中较小的依次放入helper中
        while( (i<=mid) && (j<=high) ){
            if(min2max ? (src[i] < src[j]) : (src[i] > src[j])){ //取较小（大）者放入helper中
                helper[k++] = src[i++];
            }else{
                helper[k++] = src[j++];
            }
        }

        //将左子序列中剩余部分直接拷贝到helper中
        while(i<=mid){
            helper[k++] = src[i++];
        }

        //将右子序列中剩余部分直接拷贝到helper中
        while(j<=high){
            helper[k++] = src[j++];
        }

        //将数据拷贝回array中
        for(int i=0; i< k; i++){
            src[low+i] = helper[i];
        }
    }

    //两路合并算法中的分解过程
    template <typename T>
    static void MSort(T src[], T helper[], int low, int high, bool min2max)
    {
        int mid = (low + high) /2;

        if(low  < high){ //递归结束条件，只要high>low说明还可以再分解。

            //分解为两路
            MSort(src, helper, low, mid, min2max);     //函数返回后左子序列为有序序列
            MSort(src, helper, mid + 1, high, min2max);//函数返回后右子序列为有序序列

            //合并
            Merge(src, helper, low, mid, high, min2max);
        }
    }

    template <typename T>
    static int Partition(T array[], int low, int high, bool min2max)
    {
        int pivot = low; //基准元素，将数组分为左右两个分区，并将基准放于正确的位置

        while(low < high){

            //high指针的移动,从右向左找到小于等于pivot的元素
            while((low < high) && (min2max ? (array[high] > array[pivot]):(array[high] < array[pivot]))){
                high--;
            }

            //low指针的移动,从左向右找到大于pivot的元素
            while((low < high) && (min2max ? (array[low] <= array[pivot]) : (array[low] >= array[pivot]))){
                low++;
            }

            Swap(array[low], array[high]);
        }

        //将基准元素放入low和high相遇的地方
        Swap(array[low], array[pivot]);

        return low; //返回当前基准的位置
    }

    template <typename T>
    static void Quick(T array[], int low, int high, bool min2max)
    {
        if(low < high){  //递归结束条件
            int pvIndex = Partition(array, low, high, min2max); //依基准，分成两个区

            Quick(array, low, pvIndex-1, min2max);  //左区快排（递归）
            Quick(array, pvIndex+1, high, min2max);  //右区快排（递归）
        }
    }

   //桶排序的映射函数: 计算桶号和散列函数相似
   template<typename T>
   static int getBucketIndex(T value, T min, T max, int len)
   {
       int ret = (max == min) ? 0 : (value-min) * len / (max - min);
       if (value == max)
           ret = len - 1;

       return  ret;
   }

   //桶内的插入排序
   template<typename T>
   static void putIntoBucket(BNode<T>*& bucket, BNode<T>* node,bool min2max)
   {
       BNode<T>* tmp = bucket;
       BNode<T>* prev = bucket;

       while( tmp && (min2max ? (node->data > tmp->data) : (node->data < tmp->data))){
             prev = tmp;
             tmp = tmp->next;
       }

       if(prev == tmp){
           bucket = node;
       }else{
           prev->next = node;
       }

       node->next = tmp;
   }

   //堆排序:返回左孩子结点
   static int left(int i)
   {
       return (2*i + 1);
   }

   //堆排序：返回右孩子
   static int right(int i)
   {
       return (2 * i + 2);
   }

   //堆排序(以某一结点为根的子树做堆调整（保证最大堆性质）
   template <typename T>
   static void HeapAdjust(T array[], int i, int heapSize, bool min2max)
   {
        int lf = left(i);
        int rt = right(i);

        int largest;
        T tmp;

        //比较父结点和左孩子（并将较大者的索引记录下来）
        if(lf < heapSize && (min2max ? (array[lf] > array[i]) : (array[lf] < array[i]))){
            largest = lf;
        }else{
            largest = i;
        }

        //比较父结点和右孩子（并将较大者的索引记录下来）
        if(rt < heapSize && (min2max ? (array[rt] > array[largest]) :(array[rt] < array[largest]) )){
            largest = rt;
        }

        //找到父结点与左右孩子三个结点中的最大/小值
        if(largest != i){
            //将最大/小值与父结点交换
            tmp = array[i];
            array[i] = array[largest];
            array[largest] = tmp;
            //交换后导致左右孩子的数值发生变化，对有变化结点（如左孩子）的子树进一步做堆调整。
            HeapAdjust(array, largest, heapSize, min2max);
        }
   }

   //堆排序：创建最大堆
   template <typename T>
   static void BuildHeap(T array[], int len, bool min2max)
   {
       //根据结定的数据创建最大堆（不断进行堆调整）
       for(int i=(len-2)/2; i>=0; i--){ //注意：从后向前创建堆。
                                        //叶子结点无左右孩子，不必调整。所以
                                        //i=(len-2)/2开始，跳过所有叶子结点。
           HeapAdjust(array, i, len, min2max); //对以结点i的子树进行堆调整。
       }
   }

public:
    //选择排序（O(n*n),不稳定）
    template <typename T>
    static void Select(T array[], int len, bool min2max = true)
    {
        for(int i=0; i<len-1; i++){

            //第i趟。有序区为[0,i-1],无序区为[i, len-1]
            //1.找到无序区的首元素: array[i]

            //2.从无序区中找到最小值
            int min = i; //假设：无序区中最小元素的为首元素
            for(int j=i+1; j<len; j++){
                if (min2max ? (array[j] < array[min]) : (array[j] > array[min])){
                    min = j;
                }
            }

            //3. 交换无序区中首元素和最小值的位置，将最小值放在无序区的首部
            if(i != min){
                Swap(array[i], array[min]);
            }
        }
    }

    //插入排序（O(n*n), 稳定）
    template <typename T>
    static void Insert(T array[], int len, bool min2max = true)
    {
        //1. 初始状态有序区为[0],无序区为[1..n-1]
        for(int i=1; i<len; i++){ //注意，从1开始，因为要将无序区的每个元素插入到有序区中

            //有序区[0, i-1]，无序区[i, n-1]
            //2. 取出无序区首元素，从有序区后面往前面比较依次与其比较
            T e = array[i]; //无序区首元素
            int k = i; //k记录着e最终应该放置的位置
            for(int j=i-1; (j>=0) && (min2max ? (e<array[j]) : (e>array[j]));j--){
                //3. 边比较边移动元素，e最终的位置记录在k中
                array[j+1] = array[j]; //将a[j]往后移一位
                k = j;
            }

            //4. 将e放置下来
            if(k != i){
                array[k] = e;
            }
        }
    }

    //冒泡排序: O(n*n), 稳定
    template <typename T>
    static void Bubble(T array[], int len, bool min2max = true)
    {
        bool exchange = true; //如果无序区元素己排好序，则exchange为false，
                              //否则当发生元素交换时，说明仍是无序的
        //1. 初始状态：有序区[]，无序区[0..n-1]
        for(int i=0; (i<len) && exchange; i++){
            exchange = false;
            //2. 从无序的区最后面开始，让小的元素向上冒
            for(int j=len-1; j>i; j--){
                if(min2max ? (array[j]<array[j-1]) : (array[j]>array[j-1])){ //发生逆序，则交换
                    Swap(array[j], array[j-1]);
                    exchange = true;
                }
            }
        }
    }

    //希尔排序
    template <typename T>
    static void Shell(T array[], int len, bool min2max = true)
    {
        int d = len; //增量

        do
        {
            d = d/3 + 1; //增量序列，要保证每次d增量是递减的，且最终为1

            //分成d个组（子序列），再对各个子序列进行插入排序：
            //1. 注意插入排序会将每个序列内各自的第1个元素视为有序区。各个子序列详情如下：
            //{R[0], R[0+d], R[0+2d],…,R[0+kd]} //第0个序列：有序区[0]，无序区[0+d, 0+kd]
            //{R[1], R[1+d], R[1+2d],…,R[1+kd]} //第1个序列：有序区[1]，无序区[1+d, 1+kd]
            //{R[2], R[2+d], R[2+2d],…,R[2+kd]} //第2个序列：有序区[2]，无序区[2+d, 2+kd]
            //...
            //{R[d-1], R[(d-1)+d], ,…,R[(d-1)+kd]} //第d个序列：有序区[d-1]，无序区[(d-1)+d, (d-1)+kd]
            //2. 以下是经过优化的代码，其思路是交替处理每个组，而不是处理完一组后再处理下一组。

            //i的意义：表示第(i % d)个子序列无序区首元素的位置。
            for(int i=d; i<len; i++){  //选择无序区中的第1个元素，第1个被选中的是第0个序列的无序区首元素array[d]
                //(1)i每次自增，会取出第(i % d)个序列中无序区的首元素，然后对该组再进行组内插入排序。
                //（注意，经过组内排序后该组的有序区扩大，因此交替处理分组后，当重新轮到该组时其无序区的缩小了，当然
                //首元素位置也发生了变化）

                //(2)由于i表示的是该组无序区首元素，所以i-d即有该组有序区的最后一个元素，从这元素开始向0方向依次比较
                //该组内的各个元素并进行插入操作
                int k = i;  //应插入的位置
                T e = array[i]; //取出该组无序区首元素
                for(int j=i-d; (j>=0) && (min2max ? (array[j] > e) : (array[j] < e)); j-=d){ //i为无序区首元素，i-d为有序区的最后一个元素
                   array[j+d] = array[j]; //元素后移
                   k = j;
                }

                if(k != i){
                    array[k] = e;
                }
            }

        }while (d>1);
    }

    //归并排序
    template <typename T>
    static void Merge(T array[], int len, bool min2max = true)
    {
        //申请一片与待排数据大小一样的空间
        T* helper = new T[len];

        if(helper != NULL){
            MSort(array, helper, 0, len-1, min2max);
        }

        delete[] helper;
    }

    //快速排序
    template <typename T>
    static void Quick(T array[], int len, bool min2max = true)
    {
        Quick(array, 0, len-1, min2max);
    }

    //桶排序
    template <typename T>
    static void Bucket(T array[], int len, bool min2max = true)
    {
        //创建桶（Buckets）
        BNode<T>** buckets = new BNode<T>*[len];

        //初始化Buckets,同时找到数组中的最大/小值
        T min = array[0];
        T max = array[0];
        for(int i=0; i<len; i++){
            buckets[i] = NULL;

            if(array[i] > max)
                max = array[i];

            if(array[i] < min)
                min = array[i];
        }

        //将数据放入桶中
        for(int i=0; i<len; i++){
            int pos = getBucketIndex(array[i], min, max, len);
            if(0<=pos && pos <len){
                BNode<T>* curr = new BNode<T>();
                curr->data = array[i];
                curr->next = NULL;
                putIntoBucket(buckets[pos], curr, min2max); //放入相应的桶中并做插入排序
            }
        }

        //将桶中的数据放回原数组中去
        if(min2max){
            for(int i=0, j = 0; i<len; i++){
                BNode<T>* node = buckets[i];

                while(node){
                    array[j++] = node->data;
                    node = node->next;
                }
            }
        }else{
            for(int i=len-1, j = 0; i>=0; i--){
                BNode<T>* node = buckets[i];

                while(node){
                    array[j++] = node->data;
                    node = node->next;
                }
            }
        }

        //删除各个桶
        for(int i=0; i<len; i++){
            BNode<T>* node = buckets[i];

            while(node){
                BNode<T>* tmp = node->next;

                delete node;

                node = tmp;
            }
        }

        delete[] buckets;
    }

    //堆排序
    template <typename T>
    static void Heap(T array[], int len, bool min2max = true)
    {
        BuildHeap(array, len, min2max);
        T tmp;

        for(int i=len-1; i>=0; i--){
            tmp = array[0];
            array[0] = array[i];
            array[i] = tmp;

            HeapAdjust(array, 0, i, min2max);
        }
    }

};

}

#endif // SORT_H

//main.cpp

#include <iostream>
#include "Sort.h"

using namespace std;
using namespace DTLib;

int main()
{

    //int array[]={49,38,65,97,76,13,49,27};
    int array[]={78,17,39,26,72,94,21,12,23,68};
    int len = sizeof(array)/sizeof(*array);

    Sort::Heap(array, len, false);//降序排序

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

    return 0;
}
/*测试结果
94 78 72 68 39 26 23 21 17 12
*/