算法练习：堆排序

C++代码 1：

#include <iostream>  
#include <assert.h> 
using namespace std;

//调整堆
//s:需要调整的非终端节点的位序
//len:整个待排序数组的长度
void HeapAdjust(int a[], int s, int len)
{
    int tmp = a[s];
    for(int i=s*2; i<=len; i=i*2)
    {
        int largeIndex = i;
        if(i+1 <= len && a[i+1] > a[i])
        {
            largeIndex = i+1;
        }
        if(tmp < a[largeIndex])
        {
            a[s] = a[largeIndex];
            s = largeIndex;
        }
    }
    a[s] = tmp;
}
void HeapSort(int a[], int len)
{
    //构建大根堆
    for(int i=len/2; i>=1; i--)
    {
        HeapAdjust(a, i, len);
    }
    //堆排序
    for(int i=len; i>=1; i--)
    {
        //交换每次调整后的堆的相应的第一个元素和最后一个元素
        int tmp = a[i];
        a[i] = a[1];
        a[1] = tmp;
        HeapAdjust(a, 1, i-1);
    }
}
int main() //堆排序，构建大根堆排序，输出数组元素的非递减序列
//首先构建大根堆，然后交换根元素和最后一个元素->调整剩余的(n-1)个元素为新的大根堆，如此反复直到排序结束（即只剩下最后一个未排序元素）
{
    int a[] = {0, 29, 345, 11, 3, 4, 899, 8, 1014};//因为堆排序的第一个元素序号为1，而数组的第一个元素序号为0，这里添加一个无用的首元素"0"
    int len = sizeof(a) / sizeof(int);
    
    cout << "----original----" << endl;
    for(int i=1; i<len; i++)
        cout << a[i] << " ";
    cout << endl;

    HeapSort(a, len-1);

    cout << "----result----" << endl;
    for(int i=1; i<len; i++)
        cout << a[i] << " ";
    cout << endl;

    cin.get();
    cin.get();
    return 0;
}

C++代码 2 :用递归方式实现调整堆

#include <iostream>  
#include <assert.h> 
using namespace std;

//调整堆
//s:需要调整的非终端节点的位序
//len:整个待排序数组的长度
void HeapAdjust(int a[], int s, int len)
{
	int largeIndex = s;
	int leftChildIndex = 2*s;
	if(leftChildIndex<=len && a[s]<a[leftChildIndex])
	{
		largeIndex = leftChildIndex;
	}
	int rightChildIndex = 2*s + 1;
	if(rightChildIndex<=len && a[s]<a[rightChildIndex] && a[leftChildIndex]<a[rightChildIndex])
	{
		largeIndex = rightChildIndex;
	}
	if(largeIndex != s)
	{
		int tmp = a[largeIndex];
		a[largeIndex] = a[s];
		a[s] = tmp;
		//用递归方式实现调整堆
		HeapAdjust(a, largeIndex, len);
	}
}
void HeapSort(int a[], int len)
{
	//构建大根堆
	for(int i=len/2; i>=1; i--)
	{
		HeapAdjust(a, i, len);
	}
	//堆排序
	for(int i=len; i>=1; i--)
	{
		//交换每次调整后的堆的相应的第一个元素和最后一个元素
		int tmp = a[i];
		a[i] = a[1];
		a[1] = tmp;
		HeapAdjust(a, 1, i-1);
	}
}
int main() //堆排序，构建大根堆排序，输出数组元素的非递减序列
//首先构建大根堆，然后交换根元素和最后一个元素->调整剩余的(n-1)个元素为新的大根堆，如此反复直到排序结束（即只剩下最后一个未排序元素）
{
	int a[] = {0, 29, 345, 11, 3, 4, 899, 8, 1014};//因为堆排序的第一个元素序号为1，而数组的第一个元素序号为0，这里添加一个无用的首元素"0"
	int len = sizeof(a) / sizeof(int);
	
	cout << "----original----" << endl;
	for(int i=1; i<len; i++)
		cout << a[i] << " ";
	cout << endl;

	HeapSort(a, len-1);

	cout << "----result----" << endl;
	for(int i=1; i<len; i++)
		cout << a[i] << " ";
	cout << endl;

	cin.get();
	cin.get();
    return 0;
}