常用排序算法的比较(11)

0。0 第一次写了10KB+的代码略感动。 虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

次小的记录，依此类推，直到堆中最后只有一个记录位置，得到有序序列。

HeapSort（）

for (i = n/2; i >= 1; i --) sift(p , i , n); for (i = n; i > 1; i --) { temp = p[1]; p[1] = p[i]; p[i] = temp; sift(p, 1 , i - 1); }

Sift（）//筛选 temp = p[i]; j = 2 * i;

while (j <= m) {

if (j < m && p[j] < p[j+1]) { j ++; }

if (temp < p[j]) { p[i] = p[j]; i = j; j = 2 * i; }

else break; }

p[i] = temp;

算法：当前要进行筛选的节点编号为m ， 堆中最后一个结点的编号为n,且p[m+1]至p[Num]之间的结点都已经满足堆的条件，则调整过程（函数Sift的功能）可以描述为：

（1） 设置两个指针i和j：

i指向当前的结点； j指向当前节点的左孩子结点（2*i）

（2） 比较当前结点的左右孩子的关键字的值，并用j指向关键字值较大的

孩子结点。

（3） 用当前结点的关键字与j所指向的结点关键字的值进行比较，根据比

较结果采

取相应的操作，即结束筛选或交换结点内容并继续进行筛选。

2.3.8 归并排序

归并排序的基本思想是：将待排序文件堪称为Num个长度为1的有序子文件，把这些子文件两两归并，使得[Num/2]个长度为2的有序子文件；然后再把