数据结构-堆排序 （C++代码）

解题思路:

纯正堆排，纯天然，0添加

注意事项:

参考代码:

#include <iostream>
#include <stdio.h>

using namespace std;

void swap(int arr[], int a, int b)
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

// 建堆，是一个上提过程
void heapInsert(int arr[], int index)
{
	while (arr[index] > arr[(index - 1)/2])
	{
		swap(arr, index, (index - 1)/2);
		index = (index - 1)/2;
	}
}

// 调整堆，是一个下沉过程
void heapify(int arr[], int index, int heapSize)
{
	int left = index*2 + 1;  //从0开始编号要像这样，左孩子+1右孩子+2
	while (left < heapSize)
	{
		int right = index*2 + 2;
		int largest = right < heapSize && arr[right] > arr[left] ? right : left; // 右孩子不越界 并且 右孩子的值更大
		largest = arr[largest] > arr[index] ? largest : index;
		if (index == largest) break; // index自己就是最大值，不用下沉调整
		swap(arr, index, largest);   // 最大值提到当前堆的堆顶
		index = largest;             // index自己换到最大孩子的位置
		left = index*2 + 1;          // 下沉
	}
}

void heapSort(int arr[], int length)
{
	for (int i = 0; i < length; i++)  //将数组建立成一个大根堆
		heapInsert(arr, i);
	int heapSize = length;
	swap(arr, 0, --heapSize);         //堆首尾交换
	while (heapSize > 0)
	{
		heapify(arr, 0, heapSize);    //调整为大根堆
		swap(arr, 0, --heapSize);     //堆首尾交换
	}
}

int main(void)
{
	int n = 0;
	cin >> n;
	int *a = new int[n]();
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	heapSort(a, n);
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
	delete a;
	return 0;
}