堆排序思想：
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
// // Created by liuyubobobo on 8/16/16. // #ifndef INC_08_INDEX_HEAP_SORTTESTHELPER_H #define INC_08_INDEX_HEAP_SORTTESTHELPER_H #include <iostream> #include <algorithm> #include <string> #include <ctime> #include <cassert> #include <string> using namespace std; namespace SortTestHelper { int *generateRandomArray(int n, int range_l, int range_r) { int *arr = new int[n]; srand(time(NULL)); for (int i = 0; i < n; i++) arr[i] = rand() % (range_r - range_l + 1) + range_l; 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; } int *copyIntArray(int a[], int n){ int *arr = new int[n]; copy(a, a+n, arr); 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; } bool areSameIntArrs(int* arr, int* arr2, int n){ std::sort(arr,arr+n); std::sort(arr2,arr2+n); for( int i = 0 ; i < n ; i ++ ) if( arr[i] != arr2[i] ) return false; return true; } template<typename T> void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) { T* arr2 = copyIntArray(arr, n); clock_t startTime = clock(); sort(arr, n); clock_t endTime = clock(); cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl; assert(isSorted(arr, n)); assert(areSameIntArrs(arr,arr2,n)); delete[] arr2; return; } }; #endif //INC_08_INDEX_HEAP_SORTTESTHELPER_H #include <iostream> #include <cassert> #include "SortTestHelper.h" #define Priority int using namespace std; template<typename Item> class IndexMaxHeap{ private: Item *data; int *indexes; int *reverse; int count; int capacity; void shiftUp( int k ){ while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){ swap( indexes[k/2] , indexes[k] ); reverse[indexes[k/2]] = k/2; reverse[indexes[k]] = k; k /= 2; } } void shiftDown( int k ){ while( 2*k <= count ){ int j = 2*k; if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] ) j += 1; if( data[indexes[k]] >= data[indexes[j]] ) break; swap( indexes[k] , indexes[j] ); reverse[indexes[k]] = k; reverse[indexes[j]] = j; k = j; } } public: IndexMaxHeap(int capacity){ data = new Item[capacity+1]; indexes = new int[capacity+1]; reverse = new int[capacity+1]; for( int i = 0 ; i <= capacity ; i ++ ) reverse[i] = 0; count = 0; this->capacity = capacity; } ~IndexMaxHeap(){ delete[] data; delete[] indexes; delete[] reverse; } int size(){ return count; } bool isEmpty(){ return count == 0; } // 传入的i对用户而言,是从0索引的 void insert(int i, Item item){ assert( count + 1 <= capacity ); assert( i + 1 >= 1 && i + 1 <= capacity ); i += 1; data[i] = item; indexes[count+1] = i; reverse[i] = count+1; count++; shiftUp(count); } Item extractMax(){ assert( count > 0 ); Item ret = data[indexes[1]]; swap( indexes[1] , indexes[count] ); reverse[indexes[count]] = 0; reverse[indexes[1]] = 1; count--; shiftDown(1); return ret; } int extractMaxIndex(){ assert( count > 0 ); int ret = indexes[1] - 1; swap( indexes[1] , indexes[count] ); reverse[indexes[count]] = 0; reverse[indexes[1]] = 1; count--; shiftDown(1); return ret; } Item getMax(){ assert( count > 0 ); return data[indexes[1]]; } int getMaxIndex(){ assert( count > 0 ); return indexes[1]-1; } bool contain( int i ){ assert( i + 1 >= 1 && i + 1 <= capacity ); return reverse[i+1] != 0; } Item getItem( int i ){ assert( contain(i) ); return data[i+1]; } void change( int i , Item newItem ){ assert( contain(i) ); i += 1; data[i] = newItem; // 找到indexes[j] = i, j表示data[i]在堆中的位置 // 之后shiftUp(j), 再shiftDown(j) // for( int j = 1 ; j <= count ; j ++ ) // if( indexes[j] == i ){ // shiftUp(j); // shiftDown(j); // return; // } int j = reverse[i]; shiftUp( j ); shiftDown( j ); } // test reverse index bool testReverseIndex(){ int *copyIndexes = new int[count+1]; int *copyReverseIndexes = new int[count+1]; for( int i = 0 ; i <= count ; i ++ ){ copyIndexes[i] = indexes[i]; copyReverseIndexes[i] = reverse[i]; } copyIndexes[0] = copyReverseIndexes[0] = 0; std::sort(copyIndexes, copyIndexes + count + 1); std::sort(copyReverseIndexes, copyReverseIndexes + count + 1); bool res = true; for( int i = 1 ; i <= count ; i ++ ) if( copyIndexes[i-1] + 1 != copyIndexes[i] || copyReverseIndexes[i-1] + 1 != copyReverseIndexes[i] ) res = res || false; delete[] copyIndexes; delete[] copyReverseIndexes; if( !res ){ cout<<"Error 1"<<endl; return res; } for( int i = 1 ; i <= count ; i ++ ) if( reverse[ indexes[i] ] != i ){ cout<<"Error 2"<<endl; return false; } return true; } }; template<typename T> void heapSortUsingIndexMaxHeap(T arr[], int n){ IndexMaxHeap<T> indexMaxHeap = IndexMaxHeap<T>(n); for( int i = 0 ; i < n ; i ++ ) indexMaxHeap.insert( i , arr[i] ); assert( indexMaxHeap.testReverseIndex() ); for( int i = n-1 ; i >= 0 ; i -- ) arr[i] = indexMaxHeap.extractMax(); } int main() { int n = 1000000; Priority* arr = new Priority[n]; srand(time(NULL)); for( int i = 0 ; i < n ; i ++ ) arr[i] = rand()%n; SortTestHelper::testSort("Heap Sort Using Index-Max-Heap", heapSortUsingIndexMaxHeap, arr, n); delete[] arr; return 0; }
