資訊專欄INFORMATION COLUMN
摘要：奇妙的記憶點不穩定內排序基本思想分為兩步建堆與維持堆的性質首先我們要先理解堆是什么東西堆其實就是一個完全二叉樹我們可以使用順序表存儲一個二叉樹如下圖所示來存儲其中分為最大堆最小堆而最大堆就是上頭大下頭小最小堆則反之明白了堆的定義我們就可以開
奇妙的記憶點:
不穩定
內排序
基本思想:分為兩步,建堆與維持堆的性質,首先我們要先理解堆是什么東西.
堆其實就是一個完全二叉樹,我們可以使用順序表存儲一個二叉樹,如下圖所示來存儲:
其中分為最大堆最小堆,而最大堆就是上頭大,下頭小;最小堆則反之.
明白了堆的定義我們就可以開始學習堆排序了,堆排序其實也是分為有序區與無序區,其中無序區就是我們建好的最大堆,根節點就是堆中最大的數,我們逐個讓最大元素進有序區并對堆結構進行調整,維持根節點最大的性質,直到堆中元素清空為止,就是堆排序的過程.
//工具函數
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;
}
//維持堆的性質
function heapAdjust(arr,i,len){//數組,數組下標,堆元素長度(無序區長度)
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;
}
//上述代碼就是取節點也子節點三個元素之間的最大值
if(large !== i){
swapItem(large,i,arr);
heapAdjust(arr,large,len);//防止堆性質被破壞,所以遞歸調用來維持堆性質
}
}
//建堆
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;//堆(無序區)大小
heapBuild(arr,heapSize);//建堆
for(var i=heapSize-1;i>=1;i--){
swapItem(0,i,arr);//堆頂部元素與堆底部元素交換(無序區->有序區)
//console.log(arr);
heapAdjust(arr,0,--heapSize);//維持堆性質(無序區)
}
}
//測試代碼
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)
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/80649.html
摘要：棧底是固定的，而棧頂浮動的如果棧中元素個數為零則被稱為空棧。入棧將數據保存到棧頂。鏈棧鏈棧是指棧的鏈式存儲結構，是沒有附加頭節點的運算受限的單鏈表，棧頂指針是鏈表的頭指針。 一、喜歡單挑線性表 1.線性表的特性 線性表是一個線性結構，它是一個含有n≥0個節點的有限序列。在節點中，有且僅有一個開始節點沒有前驅并有一個后繼節點，有且僅有一個終端節點沒有后繼并有一個前驅節點。其他的節點都有且...
摘要：快速排序看名字知特點就是快效率高它是處理大數據最快的排序算法之一奇妙的記憶點內排序不穩定基本思想通過一趟排序把待排序記錄分為獨立的兩部分其中一部分記錄的關鍵字都比另一部分的關鍵字笑則分別對兩部分繼續進行排序以達到整個序列有序自己的理解其實就 快速排序(Quick Sort) 看名字知特點,就是快,效率高.它是處理大數據最快的排序算法之一.奇妙的記憶點: 內排序 不穩定 基本思想 通...
摘要：區塊鏈系統首先是一個分布式系統，分布式系統的核心問題包括一致性共識一致性問題一致性問題是分布式領域最為基礎也是最重要的問題。算法與算法問題是指分布式系統中存在故障，但不存在惡意節點的場景即可能消息丟失或重復，但無錯誤消息下的共識達成問題。 區塊鏈系統首先是一個分布式系統，分布式系統的核心問題包括一致性、共識 一致性問題 一致性問題是分布式領域最為基礎也是最重要的問題。如果分布式系統能實...
摘要：目前，其已經在人臉識別等領域證明了它的強大能力，有理由相信在不久的將來，深度學習技術將為圖像視頻壓縮領域帶來更大的突破。 說到圖像壓縮算法，最典型的就是JPEG、JPEG2000等。showImg(https://segmentfault.com/img/bV1ObD?w=539&h=412); 其中JPEG 采用的是以離散余弦轉換(Discrete Cosine Transform)...
閱讀 5201·2021-10-15 09:42
閱讀 1606·2021-09-22 16:05
閱讀 3261·2021-09-22 15:57
閱讀 3396·2019-12-27 12:06
閱讀 967·2019-08-29 15:16
閱讀 2880·2019-08-26 12:24
閱讀 380·2019-08-26 12:02
閱讀 1885·2019-08-23 16:00
