堆排序及其时间复杂度

堆排序的时间复杂度，主要在 初始化堆过程 和每次 选取最大数后重新建堆的过程 ；

创新互联于2013年成立，先为龙州等服务建站，龙州等地企业，进行企业商务咨询服务。为龙州企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

推算过程：

首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

那么总的时间计算为：

其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：

除最后一项外，就是一个等比数列了，直接用求和公式：S = {a1[ 1- (q^n) ] } / (1-q)；

又因为k为完全二叉树的深度，所以

总之可以认为：k = logn （实际计算得到应该是 log(n+1) k = logn ）;

综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)

推算过程：

循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：

算法设计：从一个很大很大的数组里找前N个最大（小）数的思路之一

堆排序是啥东西啊?它在最坏情况下需要比较的次数怎么算?

堆排序

堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有

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

堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。

堆排序的思想是：

1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）

2）当未排序完时

输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。

程序如下：

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语言标准库中提供了sort包对整型，浮点型，字符串型切片进行排序，检查一个切片是否排好序，使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

关于sort包内的函数说明与使用，请查看

在这里简单讲几个sort包中常用的函数

在Go语言中，对字符串的排序都是按照字节排序，也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比较㏒₂n个元素，其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数：所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数，该函数是一个闭包，如果该有序切片是升序排列，那么在判断时使用 有序切片的元素 = 目标元素。该函数返回一个int值，表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引