文件名称：计算机不算法-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:04
数据结构 邓俊辉
第1章 绪讳 §1.1 计算机不算法 44 1.1.3 起泡排序 D. Knuth [3] 曾指出，四分之一以上的CPU时间都用于执行同一类型的计算：按照某种 约定的次序，将给定的一组元素顺序排列，比如将n个整数按通常的大小次序排成一个非降 序列。这类操作统称排序（sorting）。 就广义而言，我们今天借助计算机所完成的计算任务中，有更高的比例都可归入此类。 例如，从浩如烟海的万维网中找出与特定关键词最相关的前100个页面，就是此类计算的一 种典型形式。排序问题在算法设计与分析中扮演着重要的角色，以下不妨首先就此做一讨论。 为简化起见，这里暂且只讨论对整数的排序。 局部有序与整体有序 在由一组整数组成的序列A[0, n-1]中，满足A[i-1] A[i]的相邻元素称作顺序的； 否则是逆序的。不难看出，有序序列中每一对相邻元素都是顺序的，亦即,对任意1 i < n 都有A[i-1] A[i]；反之，所有相邻元素均顺序的序列，也必然整体有序。 扫描交换 由有序序列的上述特征，我们可以通过不断改善局部的有序性实现整体的有序：从前向 后依次检查每一对相邻元素，一旦发现逆序即交换二者的位置。对于长度为n的序列，共需 做n-1次比较和不超过n-1次交换，这一过程称作一趟扫描交换。 图1.3 通过6趟扫描交换对七个整数排序（其中已就位癿元素以深色示惲） 以图1.3(a)中由7个整数组成的序列A[0, 6] = {5, 2, 7, 4, 6, 3, 1}为例，在第 一趟扫描交换过程中，{5, 2}交换位置，{7, 4, 6, 3, 1}循环交换位置，扫描交换后的 结果如图(b)所示。 起泡排序 可见，经过这样的一趟扫描，序列未必达到整体有序。果真如此，则可对该序列再做一 趟扫描交换，比如，图(b)再经一趟扫描交换的结果如图(c)。事实上，很有可能如图(c~f) 所示需要反复进行多次扫描交换，直到如图(g)所示在序列中不再含有任何逆序的相邻元素。 多数的这类交换操作，都会使得越小（大）的元素朝上（下）方移动（习题[3]），直至它 们抵达各自应处的位置。 排序过程中，所有元素朝各自最终位置亦步亦趋的移动过程，犹如气泡在水中的上下沉 浮，起泡排序（bubblesort）算法也因此得名。