堆排序

yuananf 分享于 5天前 982阅 0人收藏此代码, 我要收藏

堆排序,喜闻乐见

#include <iostream>

using namespace std;

void printArray(int* numbers, int length);
void heapSort(int* numbers, int length);
void heapAdjust(int *src, int s, int m);
void swap(int *a, int *b);

int main()
{
	int numbers[] = {4,5,8,6,2,6,7,3,1,8,9,3};
	int length = sizeof(numbers)/sizeof(*numbers);

	cout << "before sort: ";
	printArray(numbers, length);

	heapSort(numbers, length);
	
	cout << "after sort: ";
	printArray(numbers, length);

	cin.get();
}

void printArray(int* numbers, int length)
{
	for(int i = 0; i < length; i++)
	{
		cout << numbers[i] << " ";
	}
	cout << endl;
}

void heapSort(int* numbers, int length)
{
	for(int i = length/2 - 1; i > -1; --i)  
        heapAdjust(numbers, i, length - 1);  
  
    //每次取出顶部最大的那个数放后面,再进行一次顶点调整  
    for(int i = length - 1; i > 0; i --)  
    {  
        swap(&numbers[0], &numbers[i]);  
        heapAdjust(numbers, 0, i - 1);  
    }  
}

void heapAdjust(int *src, int s, int m)  
{   
	//从s开始进行一次调整,其中m指向需要进行排序的数据中最大的下标  
    if(src == NULL) 
		return;  

    int rc = src[s];  
    for(int i = 2*s + 1; i <= m; i = 2*i + 1) //一层一层往下走  
    {  
        if(i < m && src[i] < src[i+1]) 
			i++; //让i指向最大的那个孩子
        if(rc >= src[i]) 
			break;  
  
        src[s] = src[i];  
        s = i;  
    }  
    src[s] = rc;  
}  

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
//该代码片段来自于: http://www.sharejs.com/codes/cpp/8696