C++模板堆排序

爱被打了一巴掌 2022-07-28 01:03 124阅读 0赞

# 堆排序 #

## 简介 ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

通常堆是通过一维数组来实现的。

### 表示方法 ###

<table> 
 <thead> 
 <tr> 
 <th align="left">位置</th> 
 <th align="left">在数组起始位置为0的情形中</th> 
 <th align="left">在数组起始位置为1的情形中</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="left">父节点i的左子节点位置</td> 
 <td align="left"> (2∗i+1) </td> 
 <td align="left"> (2∗i) </td> 
 </tr> 
 <tr> 
 <td align="left">父节点i的右子节点位置</td> 
 <td align="left"> (2∗i+2) </td> 
 <td align="left"> (2∗i+1) </td> 
 </tr> 
 <tr> 
 <td align="left">子节点i的父节点在位置</td> 
 <td align="left"> ⌊(i−1)/2⌋ </td> 
 <td align="left"> ⌊i/2⌋ </td> 
 </tr> 
 </tbody> 
</table>

--------------------

### 复杂度 ###

时间复杂度：  
最差时间复杂度： O(nlogn)  
最优时间复杂度： O(nlogn)  
平均时间复杂度： Θ(nlogn)

最差空间复杂度： O(n)total,O(1)auxiliary

以上整理自维基百科

--------------------

### 堆的操作 ###

**`MAX-HEAPIFY`**  
保持堆的操作。  
从元素A\[i\]、A\[LEFT(i)\]、A\[RIGHT(i)\]中找出最大的，并将其下标保存在Largest中。如果A\[i\]是最大的，则以i为根的子树已经是最大堆，程序结束。否则，i的某个子节点中有最大元素，交换A\[i\]和A\[largest\]，从而使得i及其子女满足最大堆的性质，接着需要递归调用MAX-HEAPIFY以完成对该子树递归调整。

**`BUILD-MAX-HEAP`**  
自底向上地调用MAX-HEAPIFY来将一个数组变成一个最大堆。根据堆的图形不难看出数组的n/2−n即后一半元素都是叶子节点，可以看做是只含一个元素的堆，那么我们就要对前一半的数组元素，也就是非叶子节点（非堆）调用MAX-HEAPIFY。

**`HEAPSORT`**  
假设现在我们已经通过上述两个方法有了一个最大堆，即父节点的元素都大于叶子节点的元素，那么堆的大小就等于数组长度，而根节点的元素就是该数组中值最大的元素，我们要从堆中去掉这个最大值（通过交换把它放到数组的最后），因为移除了一个元素，所以堆的大小减一，并且不再满足堆的性质，这个时候我们再对剩下的元素进行MAX-HEAPIFY操作，如此重复，最终所有的元素出堆。

--------------------

## C++模板实现堆 ##

### 代码 ###

//MySort.h
 
 #ifndef MYSORT_H_
 #define MYSORT_H_
 #include <iostream>
 #include <limits>
 namespace MySort{
 #define PARENT(i) (i/2)
 #define LEFT(i) (2*i+1)
 #define RIGHT(i) (2*i+2)
 //堆排序
 template<typename T>
 void Max_Heapify(T*arr, int i,size_t heapSize)
 {
 // size_t heapSize = sizeof(arr) / sizeof(*(arr));
 int l = LEFT(i);
 int r = RIGHT(i);
 int largest;
 if (l<heapSize && *(arr + l)>*(arr + i))
 largest = l;
 else
 largest = i;
 if (r<heapSize && *(arr + r)>*(arr + largest))
 largest = r;
 if (largest != i)
 {
 swap(*(arr + i), *(arr + largest));
 Max_Heapify(arr, largest,heapSize);
 }
 }
 template<typename T>
 void Build_Max_Heap(T*arr,size_t heapSize)
 {
 for (int i = heapSize / 2 - 1; i >= 0; i--)
 Max_Heapify(arr, i,heapSize);
 }
 template <typename T>
 void HeapSort(T *arr,size_t heapSize)
 {
 Build_Max_Heap(arr,heapSize);
 for (int i = heapSize - 1; i > 0; i--)
 {
 swap(*arr, *(arr + i));
 Max_Heapify(arr, 0,i);
 }
 }
 }//namespace MySort
 #endif

//main.cpp
 #include <iostream>
 #include "MySort.h"
 using namespace std;
 int main()
 {
 int a[] = { 3,2,1,4,5,9,8,7,6 };
 double b[] = { 5.6, 3.9, 4.1, 4.8,5.1,9.9,1.3};
 MySort::HeapSort<int>(a,sizeof(a)/sizeof(int));
 for (int i = 0; i < sizeof(a) / sizeof(int); i++)
 {
 cout << a[i] << " ";
 }
 cout << endl;
 system("PAUSE");
 return 0;
 }