排序算法pascal代码集锦(2)

while d>1 do begin d:=d div 2; repeat bool:=true; for i:=1 to n-d do if a[i]>a[i+d] then begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end; until bool; end; for i:=1 to n do write(a[i]:6); writeln; close(input);close(output); end. 堆排序与二叉树排序

1.堆排序

堆结构一定是一颗完全二叉树，并且满足节点T的值大于(小于)它两个儿子的值。当堆顶(树根)的值是整个堆里面最小的数时，这个堆称为小根堆，如果是最大的树则称之为大根堆。

上图中（a），就是一个堆，它可以被视为一棵完全二叉树。每个堆对应于一个数组（b），假设一个堆的数组A，

我们用length[A]表述数组中的元素个数，树的根为A[1]，i表示某一结点的下标，其父结点为PARENT(i)，左儿子LEFT[i]，右儿子RIGHT[i]，它们之间的关系如下： PARENT(i)=i div 2 LEFT(i)=2*i RIGHT(i)=2i + 1

堆可以在log2n的时间内完成插入节点的功能，当然能维护好堆的性质。至于如何维护堆的

性质，只需要在取出堆顶和插入节点这两个时候进行维护。下面的讨论基于大根堆。 在取出堆顶的时候，只需要把堆最后的元素放到堆顶，然后把这个放到堆顶的元素向下移动。如果这个元素小于他两个儿子中小的那个，就与其交换，如果他小于他下面儿子中大的那个，也与其交换，否则就程序结束。在加入新节点的时候，只需要把元素放到堆尾，然后判断这个节点的值是不是大于他的父节点，如果大于就进行交换，直到这个条件不成立为止，程序结束。

堆排序的思想是:

(1)建初始堆(将节点[n/2],[n/2]-1,...,3,2,1 )分别调入堆)；

(2)当未排序完时输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。 堆排序的时间复杂度为:O(nlog2n)，是一种不稳定的排序。

堆排序算法步骤（1）

堆排序算法步骤（2）

【例6】利用堆排序方法对n个数字进行排序。 程序如下: program heapsort; var n,i,temp:longint; a:array[1..100000] of longint; procedure heap(sta,en:longint); var i,j,x:longint; begin x:=a[sta]; i:=sta; j:=i*2; while (j<=en) do begin if (j二叉树排序：每一个参加排列的数据对应二叉树的一个节点，且任一节点如果有左(右)子树，则左(右)子树各节点的数据必须小(大)于该节点的数据。中序遍历排序二叉树即得排序结果。二叉树排序时间复杂度最坏情况下为O(n2)，是稳定排序。 【例7】利用二叉树排序法对n个互不相同的数字进行排序。 程序如下: program pxtree; const a:array[1..8] of integer=(10,18,3,8,12,2,7,3); type pointer=^node; node=record w:integer; right,left:pointer; end; var root,first:pointer; k:boolean; i:integer; procedure addnode(d:integer;var p:pointer); begin if p=nil then begin new(p); with p^ do begin w:=d;right:=nil;left:=nil end; if k then begin root:=p;k:=false end; end else with p^ do if d>=w then addnode(d,right) else addnode(d,left); end; procedure traveltree(p:pointer); begin with p^ do begin if left<>nil then traveltree(left); write(w:4); if right<>nil then traveltree(right); end; end; begin first:=nil;k:=true; for i:=1 to 8 do addnode(a[i],first); traveltree(root);writeln; end. 归并排序

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并。归并排序就是n个长度为1的子序列，两两归并最后变为有序的序列。 【例8】利用归并排序将n个有序数列合并成一个有序数列。 程序代码如下： program gbpx; const maxn=7; type arr=array[1..maxn] of integer; var a,b,c:arr; i:integer; procedure merge(r:arr;l,m,n:integer;var r2:arr); //合并r[l..m]、r[m+1..n] var i,j,k,p:integer; begin i:=l;j:=m+1;k:=l-1; while(i<=m) and (j<=n) do

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库排序算法pascal代码集锦(2)在线全文阅读。