首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


(2) 冒泡排序(Bubble Sort):通过相邻元素之间的比较和交换使排序码较大的元素逐渐移向序列的尾 部移动,就象气泡从水底浮向水面一样,因此而得名。

冒泡排序的一趟冒泡过程:设 1<j≤n,r[1],r[2],???,r[j]为待排序列,通过两两比较、交换,重新安排 存放顺序,使得 r[j]是序列中关键码最大的记录。 对 n 个待排序的表,第一趟冒泡得到一个关键码最大的记录 r[n],第二趟冒泡对 n-1 个待排序的表,再得 到一个关键码最大的记录 r[n-1],如此重复,直到 n 个记录按关键码有序的表,整个排序结束。 【算法描述】 Step1: j=n; //从 n 记录的表开始

Step2: if (j<2) 排序结束; Step3: i=1; Step4: if (i≥j) {一趟冒泡结束,j=j-1;冒泡表的记录数-1,转 Step2;} else 转 Step5; Step5: for if (i=1;i<=j-n;i+) 将 r[i]与 r[i+1]互换; //一趟冒泡,设置从第 1 个记录开始进行两两比较,

(r[i].key>r[i+1].key) Step6:

循环结束,转 Step4;

冒泡排序其时间复杂度为:在最坏情况下为 O(n2),最好情况下为 O(n)。 思考:若所要求排序的序列是以其链式存贮结构,其算法如何描述呢? 3. 选择排序:从欲排序的 n 个数据中,以线性查找的方式找出最小的元素和第一个元素交换,再从剩下的 (n-1)个数据中,找出最小的元素和第二个元素交换,以此类推,直到所有的元素均已排序完成。分为简 单选择排序和堆排序。 (1) 简单选择排序 操作方法:第一趟,从 n 个记录中找出关键码最小的记录与第一个记录交换;第二趟,从第二个记录开始 的 n-1 个记录中再选出关键码最小的记录与第二个记录交换;如此重复,第 i 趟,则从第 i 个记录开始的 n-i+1 个记录中选出关键码最小的记录与第 i 个记录交换,直到整个序列按关键码有序。 (2) 堆排序(Heap Sort) 设有 n 个元素的序列 k1,k2,?,kn,当且仅当满足下述关系之一时,称之为堆。

对于上述条件中第①种情况的堆称之为大根堆,相应地第②种情况称之为小根堆。见图 9-1 的图示。 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的 值,根结点的值是最小(或最大)的。

图 9-1

大根堆和小根堆图示

设有 n 个元素,将其按关键码排序。首先将这 n 个元素按关键码建成堆,将堆顶元素输出,得到 n 个元素中关键码最小(或最大)的元素。然后,再对剩下的 n-1 个元素建成堆,输出堆顶元素,得到 n 个 元素中关键码次小(或次大)的元素。如此反复,便得到一个按关键码有序的序列。称这个过程为堆排序。 因此,实现堆排序需解决两个问题: ①如何将 n 个元素的序列按关键码建成堆;② 码成为一个新堆。 首先,讨论输出堆顶元素后,对剩余元素重新建成堆的调整过程。 调整方法:设有 m 个元素的堆,输出堆顶元素后,剩下 m-1 个元素。将堆底元素送入堆顶,堆被破坏,其 原因仅是根结点不满足堆的性质。将根结点与左、右子女中较小(或小大)的进行交换。若与左子女交换, 则左子树堆被破坏,且仅左子树的根结点不满足堆的性质;若与右子女交换,则右子树堆被破坏,且仅右 子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。 称这个自根结点到叶子结点的调整过程为筛选。 【例题分析】 输出堆顶元素后,怎样调整剩余 n-1 个元素,使其按关键

图 9-2 自堆顶到叶子的调整过程 再讨论对 n 个元素初始建堆的过程。 建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。n 个

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐