資訊專欄INFORMATION COLUMN
摘要：奇妙的記憶點不穩(wěn)定內(nèi)排序基本思想分為兩步建堆與維持堆的性質(zhì)首先我們要先理解堆是什么東西堆其實就是一個完全二叉樹我們可以使用順序表存儲一個二叉樹如下圖所示來存儲其中分為最大堆最小堆而最大堆就是上頭大下頭小最小堆則反之明白了堆的定義我們就可以開
奇妙的記憶點:
不穩(wěn)定
內(nèi)排序
基本思想:分為兩步,建堆與維持堆的性質(zhì),首先我們要先理解堆是什么東西.
堆其實就是一個完全二叉樹,我們可以使用順序表存儲一個二叉樹,如下圖所示來存儲:
其中分為最大堆最小堆,而最大堆就是上頭大,下頭小;最小堆則反之.
明白了堆的定義我們就可以開始學(xué)習(xí)堆排序了,堆排序其實也是分為有序區(qū)與無序區(qū),其中無序區(qū)就是我們建好的最大堆,根節(jié)點就是堆中最大的數(shù),我們逐個讓最大元素進(jìn)有序區(qū)并對堆結(jié)構(gòu)進(jìn)行調(diào)整,維持根節(jié)點最大的性質(zhì),直到堆中元素清空為止,就是堆排序的過程.
//工具函數(shù)
function swapItem(pre,next,arr){
var temp = arr[next];
arr[next] = arr[pre];
arr[pre] = temp;
}
function getLeft(i){
return 2*i+1;
}
function getRight(i){
return 2*i+2;
}
//維持堆的性質(zhì)
function heapAdjust(arr,i,len){//數(shù)組,數(shù)組下標(biāo),堆元素長度(無序區(qū)長度)
var large,l = getLeft(i),r = getRight(i);
if(l < len&&arr[l] > arr[i]){
large = l;
}else{
large = i;
}
if(r < len&&arr[r] > arr[large]){
large = r;
}
//上述代碼就是取節(jié)點也子節(jié)點三個元素之間的最大值
if(large !== i){
swapItem(large,i,arr);
heapAdjust(arr,large,len);//防止堆性質(zhì)被破壞,所以遞歸調(diào)用來維持堆性質(zhì)
}
}
//建堆
function heapBuild(arr,len){
for(var i = Math.floor(len / 2) - 1;i>=0;i--){
heapAdjust(arr,i,len);
}
//console.log(arr);
}
//堆排序本體如下
function heapSort(arr){
var heapSize = arr.length;//堆(無序區(qū))大小
heapBuild(arr,heapSize);//建堆
for(var i=heapSize-1;i>=1;i--){
swapItem(0,i,arr);//堆頂部元素與堆底部元素交換(無序區(qū)->有序區(qū))
//console.log(arr);
heapAdjust(arr,0,--heapSize);//維持堆性質(zhì)(無序區(qū))
}
}
//測試代碼
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
heapSort(arr);
console.log(arr);
記憶點:
最佳情況：T(n) = O(nlogn)
最差情況：T(n) = O(nlogn)
平均情況：T(n) = O(nlogn)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/80649.html
摘要：棧底是固定的，而棧頂浮動的如果棧中元素個數(shù)為零則被稱為空棧。入棧將數(shù)據(jù)保存到棧頂。鏈棧鏈棧是指棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，是沒有附加頭節(jié)點的運算受限的單鏈表，棧頂指針是鏈表的頭指針。 一、喜歡單挑線性表 1.線性表的特性 線性表是一個線性結(jié)構(gòu)，它是一個含有n≥0個節(jié)點的有限序列。在節(jié)點中，有且僅有一個開始節(jié)點沒有前驅(qū)并有一個后繼節(jié)點，有且僅有一個終端節(jié)點沒有后繼并有一個前驅(qū)節(jié)點。其他的節(jié)點都有且...
摘要：快速排序看名字知特點就是快效率高它是處理大數(shù)據(jù)最快的排序算法之一奇妙的記憶點內(nèi)排序不穩(wěn)定基本思想通過一趟排序把待排序記錄分為獨立的兩部分其中一部分記錄的關(guān)鍵字都比另一部分的關(guān)鍵字笑則分別對兩部分繼續(xù)進(jìn)行排序以達(dá)到整個序列有序自己的理解其實就 快速排序(Quick Sort) 看名字知特點,就是快,效率高.它是處理大數(shù)據(jù)最快的排序算法之一.奇妙的記憶點: 內(nèi)排序 不穩(wěn)定 基本思想 通...
摘要：區(qū)塊鏈系統(tǒng)首先是一個分布式系統(tǒng)，分布式系統(tǒng)的核心問題包括一致性共識一致性問題一致性問題是分布式領(lǐng)域最為基礎(chǔ)也是最重要的問題。算法與算法問題是指分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點的場景即可能消息丟失或重復(fù)，但無錯誤消息下的共識達(dá)成問題。 區(qū)塊鏈系統(tǒng)首先是一個分布式系統(tǒng)，分布式系統(tǒng)的核心問題包括一致性、共識 一致性問題 一致性問題是分布式領(lǐng)域最為基礎(chǔ)也是最重要的問題。如果分布式系統(tǒng)能實...
摘要：目前，其已經(jīng)在人臉識別等領(lǐng)域證明了它的強大能力，有理由相信在不久的將來，深度學(xué)習(xí)技術(shù)將為圖像視頻壓縮領(lǐng)域帶來更大的突破。 說到圖像壓縮算法，最典型的就是JPEG、JPEG2000等。showImg(https://segmentfault.com/img/bV1ObD?w=539&h=412); 其中JPEG 采用的是以離散余弦轉(zhuǎn)換(Discrete Cosine Transform)...
閱讀 5257·2021-10-15 09:42
閱讀 1621·2021-09-22 16:05
閱讀 3280·2021-09-22 15:57
閱讀 3418·2019-12-27 12:06
閱讀 978·2019-08-29 15:16
閱讀 2888·2019-08-26 12:24
閱讀 391·2019-08-26 12:02
閱讀 1897·2019-08-23 16:00
