亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

基礎(chǔ)算法學(xué)習(xí)之(三):堆排序

mrli2016 / 2329人閱讀

摘要：奇妙的記憶點(diǎn)不穩(wěn)定內(nèi)排序基本思想分為兩步建堆與維持堆的性質(zhì)首先我們要先理解堆是什么東西堆其實(shí)就是一個(gè)完全二叉樹(shù)我們可以使用順序表存儲(chǔ)一個(gè)二叉樹(shù)如下圖所示來(lái)存儲(chǔ)其中分為最大堆最小堆而最大堆就是上頭大下頭小最小堆則反之明白了堆的定義我們就可以開(kāi)

奇妙的記憶點(diǎn):

不穩(wěn)定

內(nèi)排序

基本思想:

分為兩步,建堆與維持堆的性質(zhì),首先我們要先理解堆是什么東西.
堆其實(shí)就是一個(gè)完全二叉樹(shù),我們可以使用順序表存儲(chǔ)一個(gè)二叉樹(shù),如下圖所示來(lái)存儲(chǔ):

其中分為最大堆最小堆,而最大堆就是上頭大,下頭小;最小堆則反之.
明白了堆的定義我們就可以開(kāi)始學(xué)習(xí)堆排序了,堆排序其實(shí)也是分為有序區(qū)與無(wú)序區(qū),其中無(wú)序區(qū)就是我們建好的最大堆,根節(jié)點(diǎn)就是堆中最大的數(shù),我們逐個(gè)讓最大元素進(jìn)有序區(qū)并對(duì)堆結(jié)構(gòu)進(jìn)行調(diào)整,維持根節(jié)點(diǎn)最大的性質(zhì),直到堆中元素清空為止,就是堆排序的過(guò)程.

堆排序關(guān)鍵代碼 
//工具函數(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),堆元素長(zhǎng)度(無(wú)序區(qū)長(zhǎng)度)
  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é)點(diǎn)也子節(jié)點(diǎn)三個(gè)元素之間的最大值
  if(large !== i){
    swapItem(large,i,arr);
    heapAdjust(arr,large,len);//防止堆性質(zhì)被破壞,所以遞歸調(diào)用來(lái)維持堆性質(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;//堆(無(wú)序區(qū))大小
  heapBuild(arr,heapSize);//建堆
  for(var i=heapSize-1;i>=1;i--){
    swapItem(0,i,arr);//堆頂部元素與堆底部元素交換(無(wú)序區(qū)->有序區(qū))
    //console.log(arr);
    heapAdjust(arr,0,--heapSize);//維持堆性質(zhì)(無(wú)序區(qū))
  }
}
//測(cè)試代碼
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
heapSort(arr);
console.log(arr);
記憶點(diǎn):

最佳情況：T(n) = O(nlogn)

最差情況：T(n) = O(nlogn)

平均情況：T(n) = O(nlogn)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/80649.html

相關(guān)文章

  • 算法學(xué)習(xí)之數(shù)據(jù)結(jié)構(gòu)線性表、堆、棧

    摘要：棧底是固定的，而棧頂浮動(dòng)的如果棧中元素個(gè)數(shù)為零則被稱(chēng)為空棧。入棧將數(shù)據(jù)保存到棧頂。鏈棧鏈棧是指棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是沒(méi)有附加頭節(jié)點(diǎn)的運(yùn)算受限的單鏈表，棧頂指針是鏈表的頭指針。 一、喜歡單挑線性表 1.線性表的特性 線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n≥0個(gè)節(jié)點(diǎn)的有限序列。在節(jié)點(diǎn)中，有且僅有一個(gè)開(kāi)始節(jié)點(diǎn)沒(méi)有前驅(qū)并有一個(gè)后繼節(jié)點(diǎn)，有且僅有一個(gè)終端節(jié)點(diǎn)沒(méi)有后繼并有一個(gè)前驅(qū)節(jié)點(diǎn)。其他的節(jié)點(diǎn)都有且...

    huaixiaoz 評(píng)論0 收藏0

  • 基本算法學(xué)習(xí)之(二)快速排序與歸并排序

    摘要：快速排序看名字知特點(diǎn)就是快效率高它是處理大數(shù)據(jù)最快的排序算法之一奇妙的記憶點(diǎn)內(nèi)排序不穩(wěn)定基本思想通過(guò)一趟排序把待排序記錄分為獨(dú)立的兩部分其中一部分記錄的關(guān)鍵字都比另一部分的關(guān)鍵字笑則分別對(duì)兩部分繼續(xù)進(jìn)行排序以達(dá)到整個(gè)序列有序自己的理解其實(shí)就 快速排序(Quick Sort) 看名字知特點(diǎn),就是快,效率高.它是處理大數(shù)據(jù)最快的排序算法之一.奇妙的記憶點(diǎn): 內(nèi)排序 不穩(wěn)定 基本思想 通...

    Songlcy 評(píng)論0 收藏0

  • 區(qū)塊鏈學(xué)習(xí)之分布式系統(tǒng)核心問(wèn)題（四）

    摘要：區(qū)塊鏈系統(tǒng)首先是一個(gè)分布式系統(tǒng)，分布式系統(tǒng)的核心問(wèn)題包括一致性共識(shí)一致性問(wèn)題一致性問(wèn)題是分布式領(lǐng)域最為基礎(chǔ)也是最重要的問(wèn)題。算法與算法問(wèn)題是指分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點(diǎn)的場(chǎng)景即可能消息丟失或重復(fù)，但無(wú)錯(cuò)誤消息下的共識(shí)達(dá)成問(wèn)題。 區(qū)塊鏈系統(tǒng)首先是一個(gè)分布式系統(tǒng)，分布式系統(tǒng)的核心問(wèn)題包括一致性、共識(shí) 一致性問(wèn)題 一致性問(wèn)題是分布式領(lǐng)域最為基礎(chǔ)也是最重要的問(wèn)題。如果分布式系統(tǒng)能實(shí)...

    Heier 評(píng)論0 收藏0

  • 深度學(xué)習(xí)之圖像視頻壓縮技術(shù)

    摘要：目前，其已經(jīng)在人臉識(shí)別等領(lǐng)域證明了它的強(qiáng)大能力，有理由相信在不久的將來(lái)，深度學(xué)習(xí)技術(shù)將為圖像視頻壓縮領(lǐng)域帶來(lái)更大的突破。 說(shuō)到圖像壓縮算法，最典型的就是JPEG、JPEG2000等。showImg(https://segmentfault.com/img/bV1ObD?w=539&h=412); 其中JPEG 采用的是以離散余弦轉(zhuǎn)換(Discrete Cosine Transform)...

    Salamander 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<