-----------------------siwuxie095
堆排序
它的原理如下：
堆排序是指利用堆这种数据结构所设计的一种排序算法
参考链接：
参考链接1，参考链接2，参考链接3
程序 1：堆排序的实现
SortTestHelper.h：
#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H
#include <iostream>
#include <string>
#include <ctime>
#include <cassert>
#include <algorithm>
using namespace std;
//辅助排序测试
namespace SortTestHelper
{
//生成测试数据（测试用例）,返回一个随机生成的数组：
//生成有n个元素的随机数组，每个元素的随机范围为[rangeL,rangeR]
int *generateRandomArray(int n, int rangeL, int rangeR)
{
//默认rangeL要小于等于rangeR
assert(rangeL <= rangeR);
int *arr = newint[n];
//对于数组中的每一个元素，将之随机成为rangeL和rangeR之间的随机数
//先设置随机种子：这里将当前的时间作为种子来进行随机数的设置
srand(time(NULL));
for (int i = 0; i < n; i++)
{
//rand()函数+百分号+数的范围，即取中间的一个随机整数，再加上rangeL即可
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
}
return arr;
}
//生成一个近乎有序的数组
int *generateNearlyOrderedArray(int n, int swapTimes)
{
//先生成完全有序的数组
int *arr = newint[n];
for (int i = 0; i < n; i++)
{
arr[i] = i;
}
//以当前时间为随机种子
srand(time(NULL));
//再随机挑选几对元素进行交换，就是一个近乎有序的数组了
for (int i = 0; i < swapTimes; i++)
{
int posx = rand() % n;
int posy = rand() % n;
swap(arr[posx], arr[posy]);
}
return arr;
}
template<typename T>
void printArray(T arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
//经过排序算法排序后，再次确认是否已经完全排序
template<typename T>
bool isSorted(T arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
if (arr[i]>arr[i + 1])
{
return false;
}
}
return true;
}
//衡量一个算法的性能如何，最简单的方式就是看这个算法在特定数据集上的执行时间
//（1）传入排序算法的名字，方便打印输出
//（2）传入排序算法本身，即函数指针
//（3）传入测试用例：数组和元素个数
template<typename T>
void testSort(string sortName, void(*sort)(T[], int), T arr[], int n)
{
//在排序前后分别调用clock()函数
//时间差就是该排序算法执行的时钟周期的个数
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
assert(isSorted(arr, n));
//endTime 减去 startTime 转为double类型，除以 CLOCKS_PER_SEC，其中：
//
//CLOCKS_PER_SEC 是标准库中定义的一个宏，表示每一秒钟所运行的时钟周期
//的个数，而(endTime-startTime)返回的是运行了几个时钟周期
//
//这样，最终的结果就是在这段时间中程序执行了多少秒
cout << sortName << "：" << double(endTime - startTime) / CLOCKS_PER_SEC
<< "s" << endl;
}
//复制数组
int *copyIntArray(int a[], int n)
{
int *arr = newint[n];
//copy()函数在std中：
//第一个参数是原数组的头指针，
//第二个参数是原数组的尾指针，
//第三个参数是目的数组的头指针
//
//注意：copy()函数运行时会报错，需要在：
//项目->属性->配置属性->C/C++->预处理器->预处理器定义
//在其中添加：_SCL_SECURE_NO_WARNINGS
copy(a, a + n, arr);
return arr;
}
//判断两个数组是否相同
bool areSameIntArrs(int* arr, int* arr2, int n)
{
//sort()函数需要include<algorithm>
sort(arr, arr + n);
sort(arr2, arr2 + n);
for (int i = 0; i < n; i++)
{
if (arr[i] != arr2[i])
{
return false;
}
}
return true;
}
}
#endif
HeapSort.h：
#ifndef HEAPSORT_H
#define HEAPSORT_H
//堆排序：从小到大进行排序（最大堆）
template<typename T>
void heapSortUsingMaxHeap(T arr[], int n)
{
MaxHeap<T> maxheap = MaxHeap<T>(n);
for (int i = 0; i < n; i++)
{
maxheap.insert(arr[i]);
}
//将堆中的元素以从大到小的顺序取出，
//逆序放在数组中，使之从小到大进行
//排序，所以要反向遍历
for (int i = n - 1; i >= 0; i--)
{
arr[i] = maxheap.extractMax();
}
}
//堆排序：从小到大进行排序（最小堆）
template<typename T>
void heapSortUsingMinHeap(T arr[], int n)
{
MinHeap<T> minheap = MinHeap<T>(n);
for (int i = 0; i < n; i++)
{
minheap.insert(arr[i]);
}
//将堆中的元素以从小到大的顺序取出，
//顺序放在数组中
for (int i = 0; i < n; i++)
{
arr[i] = minheap.extractMin();
}
}
//此时的堆排序，相比归并排序和快速排序的速度会慢一些，
//但也是可以接受的，它可以在很快的时间里对一百万个元
//素排序完成，这是因为堆排序本身也是一个O(n*lgn)级别
//的排序算法
//
//不过，堆排序可以进行一定的优化，让它更快
//
//此时的堆排序是将数组中的所有元素使用最大堆所提供
//的插入函数，一个一个的放入堆中
//
//优化方法：
//给定一个数组，让这个数组的排列形成一个堆的形状，
//称这个过程为Heapify
//
//
//********************************************************************
//关于堆的实现（MaxHeap.h 和 MinHeap.h），详见本人博客的分类：C++远征，
//里面的"堆续2"和"堆续3"
//
//本人博客（任选一个）链接：
//https ://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
//
//
//注意：此时的堆是"堆续2"或"堆续3" 中的程序 1 和程序 3
//（不必区分堆的索引从1开始还是从0开始）
//********************************************************************
#endif
main.cpp：
#include"SortTestHelper.h"
#include"MaxHeap.h"
#include"MinHeap.h"
#include"HeapSort.h"
int main()
{
int n = 1000000;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
int *arrx = SortTestHelper::copyIntArray(arr, n);
SortTestHelper::testSort("Heap Sort Using Max-Heap", heapSortUsingMaxHeap, arr, n);
SortTestHelper::testSort("Heap Sort Using Min-Heap", heapSortUsingMinHeap, arrx, n);
delete []arr;
delete []arrx;
system("pause");
return0;
}
//********************************************************************
//关于堆的实现（MaxHeap.h 和 MinHeap.h），详见本人博客的分类：C++远征，
//里面的"堆续2"和"堆续3"
//
//本人博客（任选一个）链接：
//https ://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
//
//
//注意：此时的堆是"堆续2"或"堆续3" 中的程序 1 和程序 3
//（不必区分堆的索引从1开始还是从0开始）
//********************************************************************
运行一览：
程序 2：堆排序的优化
SortTestHelper.h：
#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H
#include <iostream>
#include <string>
#include <ctime>
#include <cassert>
#include <algorithm>
using namespace std;
//辅助排序测试
namespace SortTestHelper
{
//生成测试数据（测试用例）,返回一个随机生成的数组：
//生成有n个元素的随机数组，每个元素的随机范围为[rangeL,rangeR]
int *generateRandomArray(int n, int rangeL, int rangeR)
{
//默认rangeL要小于等于rangeR
assert(rangeL <= rangeR);
int *arr = newint[n];
//对于数组中的每一个元素，将之随机成为rangeL和rangeR之间的随机数
//先设置随机种子：这里将当前的时间作为种子来进行随机数的设置
srand(time(NULL));
for (int i = 0; i < n; i++)
{
//rand()函数+百分号+数的范围，即取中间的一个随机整数，再加上rangeL即可
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
}
return arr;
}
//生成一个近乎有序的数组
int *generateNearlyOrderedArray(int n, int swapTimes)
{
//先生成完全有序的数组
int *arr = newint[n];
for (int i = 0; i < n; i++)
{
arr[i] = i;
}
//以当前时间为随机种子
srand(time(NULL));
//再随机挑选几对元素进行交换，就是一个近乎有序的数组了
for (int i = 0; i < swapTimes; i++)
{
int posx = rand() % n;
int posy = rand() % n;
swap(arr[posx], arr[posy]);
}
return arr;
}
template<typename T>
void printArray(T arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
//经过排序算法排序后，再次确认是否已经完全排序
template<typename T>
bool isSorted(T arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
if (arr[i]>arr[i + 1])
{
return false;
}
}
return true;
}
//衡量一个算法的性能如何，最简单的方式就是看这个算法在特定数据集上的执行时间
//（1）传入排序算法的名字，方便打印输出
//（2）传入排序算法本身，即函数指针
//（3）传入测试用例：数组和元素个数
template<typename T>
void testSort(string sortName, void(*sort)(T[], int), T arr[], int n)
{
//在排序前后分别调用clock()函数
//时间差就是该排序算法执行的时钟周期的个数
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
assert(isSorted(arr, n));
//endTime 减去 startTime 转为double类型，除以 CLOCKS_PER_SEC，其中：
//
//CLOCKS_PER_SEC 是标准库中定义的一个宏，表示每一秒钟所运行的时钟周期
//的个数，而(endTime-startTime)返回的是运行了几个时钟周期
//
//这样，最终的结果就是在这段时间中程序执行了多少秒
cout << sortName << "：" << double(endTime - startTime) / CLOCKS_PER_SEC
<< "s" << endl;
}
//复制数组
int *copyIntArray(int a[], int n)
{
int *arr = newint[n];
//copy()函数在std中：
//第一个参数是原数组的头指针，
//第二个参数是原数组的尾指针，
//第三个参数是目的数组的头指针
//
//注意：copy()函数运行时会报错，需要在：
//项目->属性->配置属性->C/C++->预处理器->预处理器定义
//在其中添加：_SCL_SECURE_NO_WARNINGS
copy(a, a + n, arr);
return arr;
}
//判断两个数组是否相同
bool areSameIntArrs(int* arr, int* arr2, int n)
{
//sort()函数需要include<algorithm>
sort(arr, arr + n);
sort(arr2, arr2 + n);
for (int i = 0; i < n; i++)
{
if (arr[i] != arr2[i])
{
return false;
}
}
return true;
}
}
#endif
HeapSort.h：
#ifndef HEAPSORT_H
#define HEAPSORT_H
//堆排序：从小到大进行排序（最大堆）
template<typename T>
void heapSortUsingMaxHeap(T arr[], int n)
{
//不同的建堆方式
MaxHeap<T> maxheap = MaxHeap<T>(arr, n);
//将堆中的元素以从大到小的顺序取出，
//逆序放在数组中，使之从小到大进行
//排序，所以要反向遍历
for (int i = n - 1; i >= 0; i--)
{
arr[i] = maxheap.extractMax();
}
}
//堆排序：从小到大进行排序（最小堆）
template<typename T>
void heapSortUsingMinHeap(T arr[], int n)
{
//不同的建堆方式
MinHeap<T> minheap = MinHeap<T>(arr, n);
//将堆中的元素以从小到大的顺序取出，
//顺序放在数组中
for (int i = 0; i < n; i++)
{
arr[i] = minheap.extractMin();
}
}
//两个优化：
//（1）不同的建堆方式（引起了性能差异）
//（2）用赋值操作替代了交换操作（插入排序的优化方式）
//
//但整体上，现在的堆排序，在时间效率上依然不如归并排序和快速排序
//也正是因为如此，在系统级别实现的排序算法中，很少有使用堆排序的，
//堆这种数据结构，更多的是用于动态数据的维护
//
//
//可能有人会有疑问，为什么Heapify要比一个一个的将元素插入进堆中的
//速度要快？
//
//结论：
//（1）将n个元素逐个插入到一个空堆中，算法复杂度是O(n*lgn)
//（2）Heapify的过程，算法复杂度是O(n)
//
//
//********************************************************************
//关于堆的实现（MaxHeap.h 和 MinHeap.h），详见本人博客的分类：C++远征，
//里面的"堆续2"和"堆续3"
//
//本人博客（任选一个）链接：
//https ://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
//
//
//注意：此时的堆是"堆续2"或"堆续3"中的程序 2 和程序 4
//（不必区分堆的索引从1开始还是从0开始）
//********************************************************************
#endif
main.cpp：
#include"SortTestHelper.h"
#include"MaxHeap.h"
#include"MinHeap.h"
#include"HeapSort.h"
int main()
{
int n = 1000000;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
int *arrx = SortTestHelper::copyIntArray(arr, n);
SortTestHelper::testSort("Heap Sort Using Max-Heap", heapSortUsingMaxHeap, arr, n);
SortTestHelper::testSort("Heap Sort Using Min-Heap", heapSortUsingMinHeap, arrx, n);
delete[]arr;
delete[]arrx;
system("pause");
return0;
}
//********************************************************************
//关于堆的实现（MaxHeap.h 和 MinHeap.h），详见本人博客的分类：C++远征，
//里面的"堆续2"和"堆续3"
//
//本人博客（任选一个）链接：
//https ://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
//
//
//注意：此时的堆是"堆续2"或"堆续3"中的程序 2 和程序 4
//（不必区分堆的索引从1开始还是从0开始）
//********************************************************************
运行一览：
关于堆的实现（MaxHeap.h 和 MinHeap.h），详见本人博客的分类：C++远征，
里面的堆 续2 和 堆 续3
本人博客（任选一个）链接：
https://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
【made by siwuxie095】
