算法导论笔记一：堆排序（heapsort），快速排序（quicksort）

     《算法导论》，坊间广为流传的好书，和一些国内的算法书不一样的是，该书以伪代码的形式讲述算法，这意味着所有的算法的具体实现你需要自行编码，这有助于我们思考~~这是我看算法导论的时候对每个算法的实现，互相交流。

    堆排序（heapsort）有着O(nlg(n))的高效，堆数据结构是一种数组对象，他可以被视为一颗完全二叉树。书中每个节点与数组中存放该节点值的那个元素对应。树的每一层都是填满的，最后一层可能除外（如图）

堆有两种：最大堆和最小堆，我这里用的是最大堆，也就是根节点的值都大于子节点的值的堆。

我会在源代码里解释堆排序的步骤：

#include<stdio.h>
#include<stdlib.h>

#define parent(i) (i/2)//返回父节点的下标，此程序中未用到

#define left(i) (i*2)//返回左子节点的下标

#define right(i) (i*2+1)//返回右子节点的下标


/*ToBeLargest函数是比较每个父节点和两个
子节点，使父节点的值大于两个子节点*/
void ToBeLargest(int a[],int pos,int length)
{
    int largest = pos;
    if(left(pos)<=length && a[pos]<a[left(pos)])
        largest = left(pos);
    if(right(pos)<=length && a[largest]<a[right(pos)])
        largest = right(pos);
    if(pos != largest)
    {
        int temp = a[pos];
        a[pos] = a[largest];
        a[largest] = temp;
        ToBeLargest(a,left(pos),length);
        ToBeLargest(a,right(pos),length);
    }
    
}
/*makeHeap函数通过对每个节点调用
ToBeLargest函数建立一棵完全二叉树*/
void makeHeap(int a[],int length)
{
    int i=length;
    for(;i>0;i--)
        ToBeLargest(a,i,length);
}

/*SortHeap是堆排序的最后部分，需要一个额外的存储空间来存放结果
堆排序放弃数组下标0，从1开始用下标（因0不能得到子节点节点号）
每一次调用makeHeap能得到一个最大堆，此时的根节点是最大的，取出
放到额外存储空间，然后递减堆深度在重复makeHeap再次得到剩余元素
的最大值，以此得到一个有序序列存储到额外数组空间，该数组就是排序结果*/
void SortHeap(int a[],int length)
{
    int savelen = length;
    int *afterSort = (int *)malloc(sizeof(int)*length);//申请额外空间

    int len = length;
    int i = 0;
    while(len>=1)
    {
        makeHeap(a,length);
        afterSort[i++] = a[1];
        for(int j=0;j<length+1;j++)
            a[j] = a[j+1];
        length--;
        len--;
    }
    length = savelen;
    for(int k=0;k<length;k++)
        printf("%d ",afterSort[k]);
}

//test below

int main()
{
    int a[12] = {0,2,1,62,12,23,33,44,35,23,20,11};//第一个元素不参与排序

    SortHeap(a,11);
    return 0;
}

在SortHeap函数中的对数组的移位造成很大的效率问题，测试结果是如果对10万个无序数排序的话大概花费200s，如果采用第一个元素和最后一个元素交换这样的方法的话，结果大概只快了40s，改善不是很大。下面版本的heapsort效率很ok：见最后

quicksort是平均运行情况为O(nlg(n))的一种快速算法，和堆排序一样是属于比较排序的算法。快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。可以分为递归还是不递归两种方式来实现，先看一个递归算法：

//以p[end]作为比较元

QuickSort(int p[], int start, int end)
{
    if (start >= end) //此时无需排序，所以返回。这还保证了，如果只有2个元素时，j=end-1 =1>0

        return;
    int i = start, j = end - 1;
    int tmp;
    do
    {
        while(p[i]<p[end]){i++;}
        while(p[j]>=p[end]){j--;} // 解决相等元素问题。

         if (i<j)
           swap(p[i], p[j]);
        else
           swap(p[i], p[end]);//确定比较元的准确位置。

    }
    while(i < j);
    //至此完成了一趟快速排序得到：小于比较元的数 | 比较元 | 大于等于比较元的数


    QuickSort(p, start, i-1); //对小于比较元的数进行快速排序。

    QuickSort(p, i+1, end); //对大于等于比较元的数进行快速排序。

    // 如果i到end时，即end前的所有元素都小于比较元，会发现，i+1>end了，即递归调用时会立刻返回，所以不会发生p[i]操作越界的现象，因为根本就没机会往下走。

}

非递归的方式比较好记忆：

// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,

// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素

int Partition(int array[], int low, int high)
{
　　　 // 采用子序列的第一个元素为枢纽元素

　　　 int pivot = array[low];
　　　 while (low < high)
　　　 {
　　　　　　　 // 从后往前在后半部分中寻找第一个小于枢纽元素的元素

　　　　　　　 while (low < high && array[high] >= pivot)
　　　　　　　 {
　　　　　　　　　　　 --high;
　　　　　　　 }
　　　　　　　 // 将这个比枢纽元素小的元素交换到前半部分

　　　　　　　 Swap(&array[low], &array[high]);
　　　　　　　 // 从前往后在前半部分中寻找第一个大于枢纽元素的元素

　　　　　　　 while (low < high && array[low] <= pivot)
　　　　　　　 {
　　　　　　　　　　　 ++low;
　　　　　　　 }
　　　　　　　 // 将这个比枢纽元素大的元素交换到后半部分

　　　　　　　 Swap(&array[low], &array[high]);
　　　 }
　　　 // 返回枢纽元素所在的位置

　　　 return low;
}
// 快速排序

void QuickSort(int array[], int low, int high)
{
　　　 if (low < high)
　　　 {
　　　　　　　 int n = Partition(array, low, high);
　　　　　　　 QuickSort(array, low, n);
　　　　　　　 QuickSort(array, n + 1, high);
　　　 }
}

效率不错的heapsort：

#include <iostream>
#include <ctime>
using namespace std;
 
// 注意父子的计算方式。节点编号从0开始。

inline int parent(const int x) { return ((x-1)/2); }
inline int left(const int x) { return (2*x+1); }
inline int right(const int x) { return (2*x+2); }
 
int cmp = 0; // 总共执行比较操作的次数

int swp = 0; // 总共执行交换操作的次数

 
// 调整以i为根的子树，使之成为最大堆，size为堆的大小

void maxHeapify(int a[], int size, int i)
{
    cmp +=2;
    swp++;
 
    int l = left(i);
    int r = right(i);
    int largest = i; // 最大堆的根

   
    if( (l < size) && (a[l] > a[i]) ) largest = l;
    if( (r < size) && (a[r] > a[largest]) ) largest = r;
    if( largest != i )
    {
        swap(a[i], a[largest]); // 三个节点中较大者成为根

        maxHeapify(a, size, largest); // 可能破坏了堆性质，重新调整

    }
}
 
void buildMaxHeap(int a[], int size) // 建堆

{
    for(int i = (size-1)/2; i>=0; i--)
    {
        maxHeapify(a, size, i);
    }
}
 
void heapSort(int a[], int size) // 堆排序，(n-1)*O(lgn) = O(nlgn)

{
    swp++;
 
    buildMaxHeap(a, size);
    for(int i=size-1; i>0; i--) // 重复n-1次

    {
        swap(a[0], a[i]);
        size--;
        maxHeapify(a, size, 0); // 每次调整，花费为O(lgn)

    }
}
 
int main()
{
    //int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

    int a[100000];
    srand(time(NULL));
    for(int j = 0;j<100000;j++)
        a[j] = rand();
    long beg,end;
    time(&beg);
    heapSort(a, 100000);
    time(&end);
    cout << "总共进行比较 " << cmp << " 次，总共进行交换 " << swp << " 次" << endl;

    cout<<end-beg<<endl;
    return 0;
}