c++实现堆排序（由小到大）

这里实现了两种堆排序算法
第一种是：将n个元素逐个插入到一个空堆中，算法复杂度为O(nlogn)
第二种是：从第一个不是叶子节点的元素开始调整堆 算法复杂度为O(n)

这里还将堆排序和三路快排，归并排序做了一个比较

结果如下：

main.cpp

#include <iostream>
#include "SortTestHelper.h"
#include "Heap.h"
#include "quicksort.h"
#include "merge.h"using namespace std;template<typename T>
void heapSort1(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 heapSort2(T arr[],int n)
{MaxHeap<T> maxheap = MaxHeap<T>(arr,n);//想让正序for(int i = n - 1; i>= 0; i--)arr[i] = maxheap.extractMax();
}int main(int argc, char const *argv[])
{int n = 1000000;cout << "RandomArray" << endl;int* arr1 = SortTestHelper::generateRandomArray(n,0,n);int* arr2 = SortTestHelper::copyIntArray(arr1,n);int* arr3 = SortTestHelper::copyIntArray(arr1,n);int* arr4 = SortTestHelper::copyIntArray(arr1,n);SortTestHelper::testSort("Merge Sort",mergeSort,arr1,n);SortTestHelper::testSort("Quick Sort3Ways",quickSort3Ways,arr2,n);SortTestHelper::testSort("Heap Sort1",heapSort1,arr3,n);SortTestHelper::testSort("Heap Sort2",heapSort2,arr3,n);delete[] arr1;delete[] arr2;delete[] arr3;delete[] arr4;cout << endl;cout << "NearlyOrderedArray" << endl;int swapTimes = 100;arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);arr2 = SortTestHelper::copyIntArray(arr1,n);arr3 = SortTestHelper::copyIntArray(arr1,n);arr4 = SortTestHelper::copyIntArray(arr1,n);SortTestHelper::testSort("Merge Sort",mergeSort,arr1,n);SortTestHelper::testSort("Quick Sort3Ways",quickSort3Ways,arr2,n);SortTestHelper::testSort("Heap Sort1",heapSort1,arr3,n);SortTestHelper::testSort("Heap Sort2",heapSort2,arr3,n);delete[] arr1;delete[] arr2;delete[] arr3;delete[] arr4;cout << endl;cout << "more repeat" << endl;arr1 = SortTestHelper::generateRandomArray(n,0,10);arr2 = SortTestHelper::copyIntArray(arr1,n);arr3 = SortTestHelper::copyIntArray(arr1,n);arr4 = SortTestHelper::copyIntArray(arr1,n);SortTestHelper::testSort("Merge Sort",mergeSort,arr1,n);SortTestHelper::testSort("Quick Sort3Ways",quickSort3Ways,arr2,n);SortTestHelper::testSort("Heap Sort1",heapSort1,arr3,n);SortTestHelper::testSort("Heap Sort2",heapSort2,arr3,n);delete[] arr1;delete[] arr2;delete[] arr3;delete[] arr4;cout << endl;return 0;
}

Heap.h

#ifndef MAXHEAP_H
#define MAXHEAP_H#include<iostream>using namespace std;template<typename Item>
class MaxHeap
{
private:Item* data;  //外面的使用者不能直接使用.data来访问类中的data 和 countint count;int capacity;void shiftUp(int k){while( k > 1 && data[k/2] < data[k]) //有索引就要考虑索引越界问题{swap(data[k/2],data[k]);k /= 2;}}void shiftDown(int k){//当k有孩子就继续循环（可以判断，它只要有左孩子，就肯定有孩子）while(2*k <= count){int j = 2*k; //表示此轮循环中，data[k]和data[j]交换位置//再判断它有没有右孩子if(j + 1 <= count && data[j+1] > data[j])j += 1;if(data[k] >= data[j])break;swap(data[k],data[j]);k = j;}}public:MaxHeap(int capacity){data = new Item[capacity+1];count = 0;this->capacity = capacity;}MaxHeap(Item arr[], int n){data = new Item[n+1];capacity = n;for(int i = 0; i < n; i++)data[i+1] = arr[i];count = n;//从第一个非叶子节点开始for(int i = count / 2; i>=1 ; i--)shiftDown(i);}~MaxHeap(){delete [] data;}int size(){return count;}bool isEmpty(){return count == 0;}void insert(Item item){assert( count + 1 <= capacity);data[count+1] = item;count ++;shiftUp(count); }Item extractMax(){assert(count > 0);Item ret = data[1];swap(data[1],data[count]);count --;shiftDown(1);return ret;}public://老师是用树的方式打印出元素,我先用数组打印一下void testPrint(){if(size() >= 100)cout << "over 100 wrong!";if(typeid(Item) != typeid(int))cout << "Only for int !";cout << "The heap size is: " << size() << endl;cout << "data in heap: ";for(int i = 1; i <= size(); i++)cout << data[i]  << " ";cout << endl;cout << endl;}
};// int main(int argc, char const *argv[])
// {
// 	MaxHeap<int> maxheap = MaxHeap<int>(100);
// 	//cout << maxheap.size() << endl;// //学习一下别人的测试用例
// 	srand(time(NULL));
// 	for(int i = 0; i < 15;i++)
// 		maxheap.insert( rand()%100);
// 	maxheap.testPrint();// 	while( !maxheap.isEmpty())
// 		cout << maxheap.extractMax() << " ";// 	cout << endl;// 	return 0;
// }#endif

merge.h

#ifndef _MERGE_H
#define _MERGE_Htemplate <typename T>
void inserectsort(T arr[],int l, int r)
{for(int i = l+1;i <= r ;i++){T e = arr[i];int j;for(j = i;j > l && arr[j-1] > e;j--)arr[j] = arr[j-1];arr[j] = e;}return;
}template <typename T>//最后大合并 将arr[l,mid] 和 arr[mid+1,r]两部分进行归并
void __merge(T arr[],int l,int mid,int r)
{T aux[r-l+1];for(int i = l; i <= r;i++)aux[i-l] = arr[i]; //aux是从0开始，而arr是从l开始，所以会有l个偏移int i = l,j = mid+1;for(int k = l; k<=r; k++ ){if( i > mid ){arr[k] = aux[j - l];j++;}else if( j > r){arr[k] = aux[i-l];j++;}else if(aux[i - l] < aux[j-l]){arr[k] = aux[i-l];i++;}else{arr[k] = aux[j-l];j++;}}}template<typename T>
void __mergeSort(T arr[],int l,int r)
{//递归基的处理// if(l >= r) //表示只有一个元素或者一个都没有// 	return;//对递归基的优化if( r - l <= 15){inserectsort(arr,l,r);return;}int mid = (r+l)/2; //当r和l很大时会溢出__mergeSort(arr,l,mid); //突然明白原来是这个意思，也就是分到最后，每一次归并都需要一个辅助数组//虽然空间开销很明显会更大，但是由于我们更关注时间开销，所以这种算法我们才优先采用__mergeSort(arr,mid+1,r);//在归并前线判断一下是否已经有序了if( arr[mid] > arr[mid+1] )__merge(arr,l,mid,r);}//嗷嗷嗷，原来是通过这种方法解决了接口不统一的问题啊
template<typename T>
void mergeSort(T arr[],int n)
{__mergeSort(arr,0,n-1);
}#endif

quicksort.h

#ifndef _QUICKSORT_H
#define _QUICKSORT_H#include<iostream>using namespace std;//三路快速排序#include "SortTestHelper.h"template <typename T>
void insertionSort(T arr[],int l,int r)
{int i,j;for(i = l+1;i <= r;i++){//T e = i;T e = arr[i];for(j = i;j > l && arr[j-1] > e;j--){ //if(arr[j-1] > e)//不是arr[j] //不知道为啥这样不行//arr[e] = arr[j];arr[j] = arr[j-1];}arr[j] = e;}return;
}template <typename T>
void __quickSort3Ways(T arr[], int l, int r)
{if( r - l <= 15){insertionSort(arr,l,r);return;}//partitionswap( arr[l], arr[rand()%(r-l+1)+l] );T v = arr[l];int lt = l; //arr[l+1...lt] < vint gt = r + 1; //arr[gt...r] > vint i = l+1;//arr[lt+1,...i] = vwhile( i < gt ){if( arr[i] < v ){swap( arr[i], arr[lt+1] );lt ++;i ++;}else if( arr[i] > v){swap( arr[i], arr[gt-1] );gt --;}else{i++;}}swap( arr[l] , arr[lt]);__quickSort3Ways(arr, l, lt-1);__quickSort3Ways(arr, gt, r);
}template <typename T>void quickSort3Ways(T arr[],int n)
{srand(time(NULL));__quickSort3Ways(arr , 0 , n-1);
}#endif

SortTestHelper.h

#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H#include<iostream>
#include<ctime>
#include<cassert>using namespace std;namespace SortTestHelper{//返回指向这个数组里面第一个元素的指针int* generateRandomArray(int n,int rangeL,int rangeR){assert(rangeL <= rangeR);int *arr = new int[n];srand(time(NULL));for(int i = 0;i < n;i++)arr[i] = rand()%(rangeR - rangeL + 1) + rangeL;//这个生成的很常见，要理解return arr;}int* generateNearlyOrderedArray(int n,int swapTimes){int *arr = new int [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;return;}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;}template<typename T>void testSort(string sortName,void(*sort)(T[],int),T arr[],int n){clock_t startTime  = clock();sort(arr,n);clock_t endTime  = clock();assert(isSorted(arr,n));cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;return;}//可以将其改为模版函数 但有深拷贝问题int* copyIntArray(int a[],int n){int* arr = new int[n];copy(a,a+n,arr);return arr;}}#endif