排序——堆排序（Heap Sortd）

一时失言乱红尘 2022-08-20 11:25 18阅读 0赞

**堆排序**：是指利用堆这种数据结构所设计的排序算法，可以利用数组的特点快速定位指定索引的元素，堆分为大根堆和小根堆，是完全二叉树。

**大根堆**：每个节点上的值都不大于它父节点的值

**小根堆**：每个节点上的值都不小于它父节点的值

**完全二叉树**：除最后一层外每一层上的节点数都达到最大值，在最后一层上只缺少最右边若干个节点。

实例：

#include "stdafx.h"
    #include <iostream>
    using namespace std;
    
    //堆调整
    template<class T>
    void HeapAdjust(T data[], int i, int arrsize)
    {
    	if (i > arrsize / 2)	//i为叶子节点
    		return;
    
    	int lchiled = i * 2;		//左叶子节点
    	int rchiled = i * 2 + 1;	//右叶子节点
    	int max = i;
    
    	if (lchiled <= arrsize && data[lchiled] > data[max])
    	{
    		max = lchiled;
    	}
    	if (rchiled <= arrsize && data[rchiled] > data[max])
    	{
    		max = rchiled;
    	}
    
    	if (max != i)
    	{
    		swap(data[i], data[max]);
    		HeapAdjust(data, max, arrsize);
    	}
    }
    
    //创建堆
    template<class T>
    void BuiledHeap(T data[], int arrsize)
    {
    	for (int i = arrsize / 2; i >= 1; i--)
    	{
    		HeapAdjust(data, i, arrsize);
    	}
    }
    
    //堆排序
    template<class T>
    void HeapSort(T data[], int arrsiz)
    {
    	if (arrsiz < 2)
    		return;
    
    	BuiledHeap(data, arrsiz);
    	swap(data[1], data[arrsiz]);
    	for (int i = arrsiz - 1; i > 1; i--)
    	{
    		HeapAdjust(data, 1, i);
    		swap(data[1], data[i]);
    	}
    }
    
    template<class T>
    void Sprint(T data[], int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		cout << data[i + 1] << " ";
    	}
    
    	cout << endl;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int data[] = { 0, 3, 5, 1, 4, 6, 2 };
    	int n = sizeof(data) / sizeof(int) -1;	//数组从1开始
    	HeapSort(data, n);
    	Sprint(data, n);
    	return 0;
    }