C++實現(xiàn)堆排序?qū)嵗榻B
概述:
堆排序是利用構(gòu)建“堆”的方法確定具有最大值的數(shù)據(jù)元素,并把該元素與最后位置上的元素交換??蓪⑷我庖粋€由n個數(shù)據(jù)元素構(gòu)成的序列按照(a1,a2,...,an),按照從左到右的順序按層排列構(gòu)成一棵與該序列對應(yīng)的完全二叉樹。
一棵完全二叉樹是一個堆,當(dāng)且僅當(dāng)完全二叉樹的每棵子樹的根值ai≥其左子樹的根值a2i,同時ai≥其右子樹的根值a 2i+1 (1<i<n/2)。
實現(xiàn)堆排序需要實現(xiàn)兩個問題:
如何由無序序列建成一個堆?如何在輸出堆頂元素之后,調(diào)整剩余元素成為一個新的堆?
思路:
堆排序算法思想:1、從最后一個非葉子節(jié)點逐步到樹根,對每個子樹進行調(diào)整堆。
2、重復(fù)n-1次如下處理:將堆的根與最后一個葉子交換,除最后一個葉子之外剩余部分再調(diào)整為堆。
調(diào)整堆算法思想:1、將樹根與其左右子樹根值最大者交換;(大頂堆)
2、對交換后的左(或右)子樹重復(fù)過程1,直到左(或右)子樹為堆。
時間復(fù)雜度:O(nlogn)
代碼:
調(diào)整堆算法:
void HeapAdjust(int *array,int i,int length){ //調(diào)整堆 int leftChild=2*i+1; //定義左右孩子 int rightChild=2*i+2; int max=i; //初始化,假設(shè)左右孩子的雙親節(jié)點就是最大值 if(leftChild<length&&array[leftChild]>array[max]){ max=leftChild; } if(rightChild<length&&array[rightChild]>array[max]){ max=rightChild; } if(max!=i){ //若最大值不是雙親節(jié)點,則交換值 swap(array[max],array[i]); HeapAdjust(array,max,length); //遞歸,使其子樹也為堆 } }
堆排序算法:
void HeapSort(int *array,int length){ //堆排序 for(int i=length/2-1;i>=0;i--){ //從最后一個非葉子節(jié)點開始向上遍歷,建立堆 HeapAdjust(array,i,length); } for(int j=length-1;j>0;j--){ //調(diào)整堆 ,此處不需要j=0 swap(array[0],array[j]); HeapAdjust(array,0,j); //因為每交換一次之后,就把最大值拿出(不再參與調(diào)整堆),第三個參數(shù)應(yīng)該寫j而不是length Print(array,length); } }
完整代碼:
//堆排序 #include <iostream> using namespace std; void Print(int array[],int length){ //每執(zhí)行一次打印一次序列 for(int i=0;i<length;i++){ cout<<array[i]<<" "; } cout<<endl; } void HeapAdjust(int *array,int i,int length){ //調(diào)整堆 int leftChild=2*i+1; //定義左右孩子 int rightChild=2*i+2; int max=i; //初始化,假設(shè)左右孩子的雙親節(jié)點就是最大值 if(leftChild<length&&array[leftChild]>array[max]){ max=leftChild; } if(rightChild<length&&array[rightChild]>array[max]){ max=rightChild; } if(max!=i){ //若最大值不是雙親節(jié)點,則交換值 swap(array[max],array[i]); HeapAdjust(array,max,length); //遞歸,使其子樹也為堆 } } void HeapSort(int *array,int length){ //堆排序 for(int i=length/2-1;i>=0;i--){ //從最后一個非葉子節(jié)點開始向上遍歷,建立堆 HeapAdjust(array,i,length); } for(int j=length-1;j>0;j--){ //調(diào)整堆 ,此處不需要j=0 swap(array[0],array[j]); HeapAdjust(array,0,j); //因為每交換一次之后,就把最大值拿出(不再參與調(diào)整堆),第三個參數(shù)應(yīng)該寫j而不是length Print(array,length); } } int main(){ int array[]={49,38,65,97,76,13,27,49}; int length=sizeof(array)/sizeof(*array); Print(array,length); //先打印原始序列 HeapSort(array,length); return 0; }
運行示例:
第一行是原始序列,第二到八行分別是經(jīng)過7次調(diào)整堆所得到的序列。
到此這篇關(guān)于C++實現(xiàn)堆排序?qū)嵗榻B的文章就介紹到這了,更多相關(guān)C++堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++類與對象及構(gòu)造函數(shù)析構(gòu)函數(shù)基礎(chǔ)詳解
這篇文章主要為大家介紹了C++類與對象及構(gòu)造函數(shù)析構(gòu)函數(shù)基礎(chǔ)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-04-04詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)
這篇文章主要介紹了詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)的相關(guān)資料,這里提供實例幫助大家理解掌握這部分內(nèi)容,需要的朋友可以參考下2017-08-08詳解如何將Spire.PDF for C++集成到C++程序中
Spire.PDF for C++ 是一個專業(yè)的 PDF 庫,供開發(fā)人員在任何類型的 C++ 應(yīng)用程序中閱讀、創(chuàng)建、編輯和轉(zhuǎn)換 PDF 文檔,本文主要介紹了兩種不同的方式將 Spire.PDF for C++ 集成到您的 C++ 應(yīng)用程序中,希望對大家有所幫助2023-11-11