排序-堆排序

#include
#include
using namespace std;

/*			堆排序
	堆排序的基本思想是把数组中的元素按照一定的规则(大顶堆或小顶堆)构建出来
	然后依次输出堆顶元素并维护堆的性质直至堆顶元素全部输出完成排序

*/


//维护堆
void heapify(int arr[],int max,int i)
{
	int largest = i;						//传入数组下标

	int lson = i * 2 + 1;					//传入的下标在堆中左子节点在数组的下标
	int rson = i * 2 + 2;					//传入的下标在堆中右子节点在数组的下标

	if (lson < max && arr[largest] < arr[lson])	//父节点的值小于左子节点 -- 交换下标
		largest = lson;								
	if (rson < max && arr[largest] < arr[rson])	//同上 找出三个结点中最大的值的下标
		largest = rson;
					
	if (largest != i) 
	{
		swap(arr[i],arr[largest]);				//值交换
		heapify(arr, max, largest);				//把较小值的下标传入进行递归
	}


}

void heap_sort(int arr[],int max) 
{
	//建堆					
	//(max -1)/2为堆中最后一个有子节点的节点在数组中的下标
	
	for (int i = (max -1)/2; i >= 0; i--) { heapify(arr, max, i); }

	for (int i = max - 1; i >= 0; i--)
	{
		swap(arr[i], arr[0]);					//堆顶元素(极值)与数组最后元素交换
		heapify(arr, i, 0);						//i递减   维护堆
	}

}


//遍历数组
void print(int arr[], int max)
{
	for (int i = 0; i < max; i++) { cout << arr[i] << "  "; }
	cout << endl;
}

void test() 
{
	srand((unsigned int)time(NULL));

	int arr[20] = { 0 };

	for (int i = 0; i < 20; i++) { arr[i] = rand() % 100 + 1; }

	print(arr, sizeof(arr)/ sizeof(int));
	
	heap_sort(arr, sizeof(arr)/sizeof(int));
	
	print(arr, sizeof(arr)/ sizeof(int));
}



int main()
{
	test();
	system("pause");
	return 0;
}