排序-堆排序

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