C++——算法基础之排序——堆排序

今天，大白跟大家玩玩堆排序。

基本思想：

堆排序是利用堆（大根堆或者小根堆）的特点进行排序。。。。啪啦啪啦一大堆。。。。

（以建最小堆为例）

简言之，就是将无序区看成一个完全二叉树，利用完全二叉树用数组存储是的特点，进行排序。

建堆：从序列的末尾开始，先找出孩子中的较小值，然后和双亲比较，如果小于双亲，则交换位置。

排序：进行 n - 1次建堆，每次建堆完成后（此时，序列首位为最小值），将无序区的首位和末尾交换位置，然后使 n--；直至n = 1.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

void swap (int *arr, int i);
void heapSort (int *arr, int n);
void sift_minheap (int *arr, int n);

void sift_minheap (int *arr, int n)
{
	if((n - 1) % 2 == 0)
	{
		for(int i = n - 1; i > 0; i -= 2)
		{
			swap (arr, i);
		}
	}
	else if(n > 1)
	{
		if(arr[(n - 1) / 2] > arr[n - 1])
		{
			int temp = arr[(n - 1) / 2];
			arr[(n - 1) / 2] = arr[n - 1];
			arr[n - 1] = temp;
		}
		for(int i = n - 2; i > 0; i -= 2)
		{
			swap (arr, i);
		}
	}
}

void swap (int *arr, int i)
{
	if(arr[i] < arr[i - 1])
	{
		if(arr[(i - 1) / 2] > arr[i])
		{
			int temp = arr[(i - 1) / 2];
			arr[(i - 1) / 2] = arr[i];
			arr[i] = temp;
		}
	}
	else
	{
		if(arr[(i - 1) / 2] > arr[i - 1])
		{
			int temp = arr[(i - 1) / 2];
			arr[(i - 1) / 2] = arr[i - 1];
			arr[i - 1] = temp;
		}
	}
}

void heapSort (int *arr, int n)
{
	for(int i = n; i > 1; i--)
	{
		sift_minheap (arr, i);
		int temp = arr[i - 1];
		arr[i - 1] = arr[0];
		arr[0] = temp;
	}
}

int main ()
{
	int keys[] = { 88, 22, 66, 88, 66, 33, 30, 65, 57, 69 };
	heapSort (keys, 10);
	for(int i = 0; i < 10; i++)
	{
		cout << keys[i] << "  ";
	}
	cout << endl;
	return 0;
}