C++實現(xiàn)堆排序

發(fā)布時間：2020-04-18 21:44:29 來源：網(wǎng)絡(luò) 閱讀：442 作者：zgw285763054 欄目：編程語言

/*堆排序*/

#include <iostream>
using namespace std;

void AdjustDown(int* array, size_t size, size_t parent)
{
	size_t child = parent*2 + 1;

	while (child < size)
	{
		if (child+1 < size 
			&& array[child] < array[child+1])
		{
			++child;
		}

		if (array[child] > array[parent])
		{
			swap(array[child], array[parent]);

			parent = child;
			child = parent*2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* array, size_t size)
{
	//建堆
	for (int i = (size-2)/2; i >= 0; --i)
	{
		AdjustDown(array, size, i);
	}

	//選數(shù)據(jù)排序
	for (size_t i = 0; i < size; ++i)
	{
		swap(array[0], array[size-i-1]);

		AdjustDown(array, size-i-1, 0);
	}
}

向AI問一下細(xì)節(jié)

C++實現(xiàn)堆排序

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽