欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現(xiàn)堆排序?qū)嵗榻B

 更新時間:2021年12月22日 09:21:55   作者:NEU!  
大家好,本篇文章主要講的是C++實現(xiàn)堆排序?qū)嵗榻B,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽

概述:

堆排序是利用構(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ǔ)詳解

    這篇文章主要為大家介紹了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ù)

    這篇文章主要介紹了詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)的相關(guān)資料,這里提供實例幫助大家理解掌握這部分內(nèi)容,需要的朋友可以參考下
    2017-08-08
  • C++實現(xiàn)漢諾塔算法經(jīng)典實例

    C++實現(xiàn)漢諾塔算法經(jīng)典實例

    這篇文章主要介紹了C++實現(xiàn)漢諾塔算法經(jīng)典實例,代碼簡潔高效,對于學(xué)習(xí)算法的朋友有一定的借鑒價值,需要的朋友可以參考下
    2014-07-07
  • C++OOP對象和類的詳細講解

    C++OOP對象和類的詳細講解

    這篇文章主要介紹了C++面相對象編程中的類與對象的特性與概念,OOP面向?qū)ο笳Z言相對C語言這樣面相過程的語言來說具有類和對象以及方法這樣的特性,需要的朋友可以參考下
    2021-08-08
  • C++詳解如何實現(xiàn)兩個線程交替打印

    C++詳解如何實現(xiàn)兩個線程交替打印

    這篇文章主要介紹了使用C++庫實現(xiàn)兩個線程交替打印,一個線程打印奇數(shù)、一個線程打印偶數(shù),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-08-08
  • C++?pimpl機制詳細講解

    C++?pimpl機制詳細講解

    PIMPL?是?C++?中的一個編程技巧,意思為指向?qū)崿F(xiàn)的指針。具體操作是把類的實現(xiàn)細節(jié)放到一個單獨的類中,并用一個指針進行訪問
    2022-08-08
  • C語言利用EasyX實現(xiàn)繪制足球圖案

    C語言利用EasyX實現(xiàn)繪制足球圖案

    這篇文章主要為大家詳細介紹了C語言如何利用EasyX繪圖庫實現(xiàn)繪制一個簡單的足球圖案,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下
    2022-11-11
  • c++仿函數(shù)和函數(shù)適配器的使用詳解

    c++仿函數(shù)和函數(shù)適配器的使用詳解

    這篇文章主要介紹了c++仿函數(shù)和函數(shù)適配器的使用詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • 詳解如何將Spire.PDF for C++集成到C++程序中

    詳解如何將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
  • C語言的動態(tài)內(nèi)存管理你了解嗎

    C語言的動態(tài)內(nèi)存管理你了解嗎

    這篇文章主要為大家詳細介紹了C語言的動態(tài)內(nèi)存管理,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03

最新評論