第九章 排序(3)

1湖南理工学院信息与通信工程学院数据结构第九章排序插入排序交换排序选择排序归并排序外部排序2湖南理工学院信息与通信工程学院数据结构9.7外部排序基本思想：两两比较待排序的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。按照排序的策略不同：冒泡排序快速排序3湖南理工学院信息与通信工程学院数据结构冒泡排序基本思想：交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。1625990231625909923从最底部的元素开始比较两个元素中较小的会冒到顶部，而较大的会沉到底部该过程将被重复执行，直到所有元素都被排序1690162325904湖南理工学院信息与通信工程学院数据结构for(i=0;i4;i++){//内层循环控制冒出的究竟是哪个泡泡for(intj=4;ji;j--){if(a[j]a[j-1]){inttemp;temp=a[j];a[j]=a[j-1];a[j-1]=temp;}}}冒泡排序代码实现时间复杂度：O（n2）冒泡排序是一种稳定的排序方法。5湖南理工学院信息与通信工程学院数据结构快速排序首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key初始时令i=s,j=t(1)首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换(2)再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换(3)重复上述两步，直至i==j为止(4)再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止6湖南理工学院信息与通信工程学院数据结构13652750384955ji1338652750495513652750493855jjiiijijjj7湖南理工学院信息与通信工程学院数据结构例初始关键字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849506576974927ijijij4965ji1349ij4997ij8湖南理工学院信息与通信工程学院数据结构快速排序性能分析最坏情况：每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为O(n2)。最好情况：每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。平均情况：为O(nlog2n)。)()1(21211nOnninni=-=--=）（9湖南理工学院信息与通信工程学院数据结构9.3选择排序选择排序的主要操作是选择，其主要思想是:每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。直接选择排序按照排序的策略不同：堆排序10湖南理工学院信息与通信工程学院数据结构直接选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束11湖南理工学院信息与通信工程学院数据结构0821i=2最小者08交换21,08最小者16交换25,16最小者21交换49,212128i=12516490808i=3210828492128491625162512湖南理工学院信息与通信工程学院数据结构i=4最小者25交换25,28i=5最小者28不交换492108281625254921081628252849210816282528无序区只有一个记录例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：1327384965769714湖南理工学院信息与通信工程学院数据结构直接选择排序性能分析最坏情况：3(n-1)次移动次数：最好情况（正序）：0次空间性能：需一个辅助空间。稳定性：是一种稳定的排序算法。45231152341253412354123451234比较次数：)()1(21211nOnninni=-=--=）（简单选择排序的时间复杂度为O(n2)。15湖南理工学院信息与通信工程学院数据结构堆排序堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。182032364525385040281.小根堆的根结点是所有结点的最小者。2.较小结点靠近根结点，但不绝对。16湖南理工学院信息与通信工程学院数据结构503845402836322018281.大根堆的根结点是所有结点的最大者。2.较大结点靠近根结点，但不绝对。堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。17湖南理工学院信息与通信工程学院数据结构将堆用顺序存储结构来存储，则堆对应一组序列。503845402836322018285038453236402820182812345678910采用顺序存储18湖南理工学院信息与通信工程学院数据结构堆调整在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？28363216182532161825362819湖南理工学院信息与通信工程学院数据结构如何由一个无序序列建成一个堆28251632183616321628251836253216281836252832362816182520湖南理工学院信息与通信工程学院数据结构如何处理堆顶记录323628161825362832251816123456对应交换162832251836123456对应32162836182521湖南理工学院信息与通信工程学院数据结构如何调整剩余记录，成为一个新堆32162836182516281632361825283236181625整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。22湖南理工学院信息与通信工程学院数据结构例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13273849502765769713输出：13276549502738769713输出：13273823湖南理工学院信息与通信工程学院数据结构4965502738769713输出：1327387665502738499713输出：132738495065762738499713输出：132738499765762738495013输出：13273849506597762738495013输出：13273849509765762738495013输出：13273849506524湖南理工学院信息与通信工程学院数据结构7665972738495013输出：1327384950659765762738495013输出：132738495065769765762738495013输出：132738495065769725湖南理工学院信息与通信工程学院数据结构9.4归并排序归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。归并：将两个或两个以上的有序序列合并成一个有序序列的过程。基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。26湖南理工学院信息与通信工程学院数据结构602031544556520605314455656020315445565ij5kj20i31j6027湖南理工学院信息与通信工程学院数据结构例初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]时间复杂度：T(n)=O(nlog2n)空间复杂度：S(n)=O(n)28湖南理工学院信息与通信工程学院数据结构排序方法比较排序方法选择主要考虑：待排序记录个数n记录本身的大小关键字的分布情况对排序稳定性要求排序方法平均时间最坏情况最好情况辅助空间稳定性插入排序O(n2)O(n2)O(n)O(1)√选择排序O(n2)O(n2)O(n2)O(1)√冒泡排序O(n2)O(n2)O(n)O(1)√快速排序O(nlogn)O(n2)O(nlogn)O(nlogn)×归并排序O(nlogn)O(nlogn)O(nlogn)O(n)√堆排序O(nlogn)O(nlogn)O(nlogn)O(1)×基数排序O(d*n)O(d*n)O(d*n)O(n)√