堆排序及其時(shí)間復(fù)雜度

堆排序的時(shí)間復(fù)雜度，主要在 初始化堆過程 和每次 選取最大數(shù)后重新建堆的過程 ；

創(chuàng)新互聯(lián)于2013年成立，先為龍州等服務(wù)建站，龍州等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為龍州企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

推算過程：

首先要理解怎么計(jì)算這個(gè)堆化過程所消耗的時(shí)間，可以直接畫圖去理解；

假設(shè)高度為k，則從倒數(shù)第二層右邊的節(jié)點(diǎn)開始，這一層的節(jié)點(diǎn)都要執(zhí)行子節(jié)點(diǎn)比較然后交換（如果順序是對(duì)的就不用交換）；倒數(shù)第三層呢，則會(huì)選擇其子節(jié)點(diǎn)進(jìn)行比較和交換，如果沒交換就可以不用再執(zhí)行下去了。如果交換了，那么又要選擇一支子樹進(jìn)行比較和交換；

那么總的時(shí)間計(jì)算為：

其中 i 表示第幾層，2^( i - 1) 表示該層上有多少個(gè)元素，( k - i) 表示子樹上要比較的次數(shù)，如果在最差的條件下，就是比較次數(shù)后還要交換；因?yàn)檫@個(gè)是常數(shù)，所以提出來后可以忽略；

這個(gè)等式求解，我想高中已經(jīng)會(huì)了：等式左右乘上2，然后和原來的等式相減，就變成了：

除最后一項(xiàng)外，就是一個(gè)等比數(shù)列了，直接用求和公式：S = {a1[ 1- (q^n) ] } / (1-q)；

又因?yàn)閗為完全二叉樹的深度，所以

總之可以認(rèn)為：k = logn （實(shí)際計(jì)算得到應(yīng)該是 log(n+1) k = logn ）;

綜上所述得到：S = n - longn -1，所以時(shí)間復(fù)雜度為：O(n)

推算過程：

循環(huán) n -1 次，每次都是從根節(jié)點(diǎn)往下循環(huán)查找，所以每一次時(shí)間是 logn，總時(shí)間：

算法設(shè)計(jì)：從一個(gè)很大很大的數(shù)組里找前N個(gè)最大（小）數(shù)的思路之一

堆排序是啥東西啊?它在最壞情況下需要比較的次數(shù)怎么算?

堆排序

堆：設(shè)有數(shù)據(jù)元素的集合（R1,R2,R3,...Rn)它們是一棵順序二叉樹的結(jié)點(diǎn)且有

Ri=R2i 和Ri=R2i+1(或=)

堆的性質(zhì)：堆的根結(jié)點(diǎn)上的元素是堆中的最小元素，且堆的每一條路徑上的元素都是有序的。

堆排序的思想是：

1）建初始堆（將結(jié)點(diǎn)[n/2],[ n/2]-1,...3,2,1分別調(diào)成堆）

2）當(dāng)未排序完時(shí)

輸出堆頂元素，刪除堆頂元素，將剩余的元素重新建堆。

程序如下：

program duipx;

const n=8;

type arr=array[1..n] of integer;

var a:arr;i:integer;

procedure sift(var a:arr;l,m:integer);

var i,j, t:integer;

begin

i:=l;j:=2*i;t:=a[i];

while j=m do

begin

if (jm) and (a[j]a[j+1]) then j:=j+1;

if ta[j] then

begin a[i]:=a[j];i:=j;j:=2*i; end

else exit;

a[i]:=t;

end;

end;

begin

for i:=1 to n do read(a[i]);

for i:=(n div 2) downto 1 do

sift(a,i,n);

for i:=n downto 2 do

begin

write(a[1]:4);

a[1]:=a[i];

sift(a,1,i-1);

end;

writeln(a[1]:4);

end.

Go語言 排序與搜索切片

Go語言標(biāo)準(zhǔn)庫中提供了sort包對(duì)整型，浮點(diǎn)型，字符串型切片進(jìn)行排序，檢查一個(gè)切片是否排好序，使用二分法搜索函數(shù)在一個(gè)有序切片中搜索一個(gè)元素等功能。

關(guān)于sort包內(nèi)的函數(shù)說明與使用，請(qǐng)查看

在這里簡(jiǎn)單講幾個(gè)sort包中常用的函數(shù)

在Go語言中，對(duì)字符串的排序都是按照字節(jié)排序，也就是說在對(duì)字符串排序時(shí)是區(qū)分大小寫的。

二分搜索算法

Go語言中提供了一個(gè)使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比較㏒?n個(gè)元素，其中n為切片中元素的總數(shù)。

sort.Search(size,fn)函數(shù)接受兩個(gè)參數(shù)：所處理的切片的長度和一個(gè)將目標(biāo)元素與有序切片的元素相比較的函數(shù)，該函數(shù)是一個(gè)閉包，如果該有序切片是升序排列，那么在判斷時(shí)使用 有序切片的元素 = 目標(biāo)元素。該函數(shù)返回一個(gè)int值，表示與目標(biāo)元素相同的切片元素的索引。

在切片中查找出某個(gè)與目標(biāo)字符串相同的元素索引