数据结构之排序课件(编辑修改稿)

数据结构之排序课件(编辑修改稿)内容摘要：

个一维数组 r中，具体的做法是：设两个指示器 i和 j，初始时 i指向数组中的第一个数据， j指向最末一个数据。 i先不动使 j逐步前移，每次对二者所指的数据进行比较，当遇到 r[i]大于 r[j]的情况时，就将二者对调位置；然后令 j固定使 i逐步后移做数据比较，当遇到 r[i]大于 r[j] 时，又进行位置对调；然后又是 i不动使 j前移作数据比较； …… ； 如此反复进行，直至 i与 j两者相遇为止。 图 过程。 图中括号中的数据表示正进行比较的两个数据，左面一个的下标为 i，右面一个的下标为j。 最后一行只有一个括号，说明 i与 j相等了，此单元即是数据 13的最终位置。 图 一趟数据比较和互换 ( 13 ) 15 7 10 30 4 8 ( 25 ) ( 13 ) 15 7 10 30 4 ( 8) 25 8 ( 15 ) 7 10 30 4 ( 13 ) 25 8 ( 13 ) 7 10 30 ( 4) 15 25 8 4 ( 7) 10 30 ( 13 ) 15 25 8 4 7 ( 10 ) 30 ( 13 ) 15 25 8 4 7 10 ( 30 ) ( 13 ) 15 25 8 4 7 10 ( 13 ) 30 15 25 一趟快速排序 void quickOnePass ( r[ ], low, hig) { i=low, j=hig。 x=r[i]。 do { while( r[j].key= amp。 amp。 (ij)) j。 if (ij) /*已找到了满足 { r[i]=r[j]。 /*r[j].keyx的 r[j] i++。 } 快速排序算法续 while (r[i].key =) amp。 amp。 ( ij )) i++。 if (ij) /*已找到了满足 r[i].keyx的 r[i] { r[j]=r[i]。 j。 } } while (ij)。 r[i]=x。 return(i)。 } 整个快速排序过程如下： Void quicksort(r[], low, hig) { int k。 If(lowhig) { k=quickonepass(r, low, hig)。 Quicksort(r, low, k1)。 Quicksort(r, k+1, hig)。 } } 快速排序分析 当初始序列有序或基本有序时，快速排序就接近于冒泡排序了，其时间复杂度为 O(n*n). 该算法是霍尔 1962年提出的。 在所有已发表的排序算法中，该算法是研究最深的。 当时他就发现了以上的问题，他在文章中建议用两种方法改进：产生一个随机数，或选择一个小样本中值。 1969年，辛格尔顿就遵循了这一建议，采用R[1].key, R[n].key, R[n/2].key的中间值，故称作“三者取中”法。 快速排序分析 快速排序的平均时间复杂性为 O(nlogn)，对 n较大的情况，这种算法是平均速度最快的排序算法，但当 n很小时，此方法往往比其他简单排序方法还要慢。 快速排序更偏爱一个“ 杂乱无章 ”的序列。 快速排序是不稳定的。 返回 堆排序 堆的概念 堆排序（ Heap Sort）是利用二叉树的一种排序方法。 （大根）堆（ Heap）：在一棵完全二叉树中，每个结点如果有儿子的话，此结点必须大于或等于其儿子结点。 由于堆是完全二叉树，采用将结点顺序编号存入一维数组中的表示法比链接表示法节省存储空间，也便于计算。 设某堆的结点数共有 n个，顺序将它们存入一维数组 r[] 中。 根据顺序表示二叉树的特点，除下标为 1的结点 (根结点 )没有父结点以外，其余下标为 j 的结点（ 2≤j≤n）都有父结点，父结点的下标为 i=。  2/j由堆的定义可知，其根结点（即在数组中下标为 1的结点）具有最小的关键字，堆排序就是利用这一特点进行的。 实现堆排序需要解决两个问题： 1. 把一组待排序的元素构建成堆； 2. 输出堆顶后 , 如何将剩下的 n1个元素 调整成一个新的堆 . 先介绍第 2个问题 设堆顶输出后，以堆的最后一个元素代替之，此时的左子树、右子树都是堆，则只需自上而下地调整即可。 这个调整过程称为“ 筛选 ”。 例： void sift (r[], i, m) /*把 R[i： m]看成完全二叉树 ， 以 { j=2*i。 /*R[i+1]和 R[i+2]为根的左右子树是 x=r[i]。 /*堆 ， 现要调整 R[i]， 使整个序列 while (j=m) /*R[i： m]成为一个堆 { if ((jm amp。 amp。 r[j].keyr[j+1].key)) j++。 if (r[j].key) /*j为左右儿子中较小者的下标 { r[i]=r[j]。 /*左右儿子中较小者上移 ， i=j。 j=2*i } else break。 /*x不大于左右儿子 ， 即已找到 } /*了合适的位置 i， 循环结束 r[i]=x。 /*把 x放在 i的位置上 } 筛选算法 介绍第 1个问题，即把一个无序的序列建成一个堆。 把一个 n个元素的无序序列看成一棵完全二叉树，则最后一个内部结点的下标是 n/2 .因此，只需从第 n/2 个元素开始，直到第 1个元素，依次调用 sift, 即可建成一个堆。 例： 堆排序算法 void heapsort (r[], n) { int i。 for (i=n/2。 i=1。 i) sift (r, i, n)。 /* 初始建堆 */ for (i=n。 i1。 i) { r[1]r[i]。 /*堆顶元素和最后一个 sift (r, 1, i1)。 /*元素交换 } } 堆排序算法分析 其运行时间主要消耗在建初始堆和进行反复的筛选上。 对 n个元素，树的深度 k=log2n +1，筛选算法中关键字的比较次数最多为 2（ k1），共调用了 n1次，所以总的比较次数小于 2n（ log2n）次；在建初始堆。