首页 > 代码库 > 算法练习:堆排序

算法练习:堆排序

 

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

 

算法练习:堆排序