------------------siwuxie095
索引堆排序
程序：
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 heapSortUsingMaxIndexHeap(T arr[],int n)
{
MaxIndexHeap<T> maxIndexHeap = MaxIndexHeap<T>(n);
for (int i =0; i < n; i++)
{
maxIndexHeap.insert(i, arr[i]);
}
for (int i = n -1; i >= 0; i--)
{
arr[i] = maxIndexHeap.extractMax();
}
}
//索引堆排序：从小到大进行排序（最小堆）
template<typename T>
void heapSortUsingMinIndexHeap(T arr[],int n)
{
MinIndexHeap<T> minIndexHeap = MinIndexHeap<T>(n);
for (int i =0; i < n; i++)
{
minIndexHeap.insert(i, arr[i]);
}
for (int i =0; i < n; i++)
{
arr[i] = minIndexHeap.extractMin();
}
}
//**********************************************************************************
//关于索引堆的实现（MaxIndexHeap.h和 MinIndexHeap.h），详见本人博客的分类：C++远征，
//里面的"堆续5"、"堆续6"、"堆续7"和"堆续8"
//
//本人博客（任选一个）链接：
//https ://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
//**********************************************************************************
#endif
main.cpp：
#include"SortTestHelper.h"
#include"MaxIndexHeap.h"
#include"MinIndexHeap.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 Index-Max-Heap",
heapSortUsingMaxIndexHeap, arr, n);
SortTestHelper::testSort("Heap Sort Using Index-Min-Heap",
heapSortUsingMaxIndexHeap, arrx, n);
delete []arr;
delete []arrx;
system("pause");
return0;
}
//**********************************************************************************
//关于索引堆的实现（MaxIndexHeap.h和 MinIndexHeap.h），详见本人博客的分类：C++远征，
//里面的"堆续5"、"堆续6"、"堆续7"和"堆续8"
//
//本人博客（任选一个）链接：
//https ://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
//**********************************************************************************
关于索引堆的实现（MaxIndexHeap.h 和 MinIndexHeap.h），详见本人
博客的分类：C++远征，里面的 堆 续5 、 堆 续6 、堆 续7 和 堆 续8
本人博客（任选一个）链接：
https://www.baidu.com/s?ie=UTF-8&wd=siwuxie095
【made by siwuxie095】
