必威体育精装版排序与选择.ppt

6.1 简单排序算法 6.1.1 冒泡排序 基本思想： 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序(即：a[0].keya[1].key)，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 算法描述 6.1 简单排序算法 6.1.2 直接插入排序 基本思想： 整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 6.1 简单排序算法 6.1.3 选择排序 基本思想： 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换； 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换； 重复上述操作，共进行n-1趟排序后，排序结束。 6.2 快速排序算法 6.2.0 算法的基本策略思想 ——非平衡、预处理二分分治 第一步 对于给定的数组a[p:r],pr,以x=a[p]为基准，调整a[p:q]，使得能够确定一个下标q,p≦q≦r，将a[p:r]分成3段,即：a[p:q-1]，a[q]和a[q+1:r], 满足a[p:q-1]中的任一元素都不大于x,同时， a[q+1:r]中的任一元素都不小于x；这叫划分(Partition) 。 第二步 将这种策略依次分别递归地运用于a[p:q-1]和 a[q+1:r], 使得a[p:q-1]和a[q+1:r]分别从小到大排好序;从而达到数组a[p:r]从小到大就地排好序。 6.2 快速排序算法 6.2.1 快速排序(QuickSort)算法的实现: //对a[0:n-1]快速排序只要调用QuickSort (a,0,n-1); 6.2.2 划分(Partition) 的实现 6.2.3 算法的性能分析 快速排序的运行时间与划分是否平衡密切相关。 对于输入序列a[0:n-1]，Partition的计算时间显然为O(n)。它的最坏情况发生在划分产生的两段分别包含n-1个元素和1个元素的时候。如果算法每一次调用Partition都出现这种不平衡划分，则QuickSort (a,0,n-1)的耗时T(n)满足 算法的性能分析： 在最好情况下，每次划分所取的基准都恰好为中值，即每次划分都产生大小相当的2段，则T(n)满足 6.2 快速排序算法 6.2.4 随机快速排序算法 (1) 算法的动因 可以证明，如果在a[0:n-1]中选择的作为划分(Partition) 的基准值是随机的，那么，快速排序算法在平均情况下的时间复杂性就是O(nlogn) ，即达到基于比较的排序算法类中的最好水平。 因此，人们提出:划分(Partition) 的基准值不固定为数组的第1个值而是随机在a[p:r]中地挑选。其他思想不变，这就是随机快速排序算法。 6.2.4 随机快速排序算法(续) (2)随机版的划分的实现 6.2.4 随机快速排序算法(续) （3）随机快速排序算法的实现 6.3 合并排序算法(非就地) 6.3.1 递归版的合并排序算法 (1)基本策略思想——平衡、简单二分分治： 将待排序元素序列简单地分成大小大致相等的左右两段，接着依次分别对这两段子序列递归地进行合并排序，然后利用这两段子序列已得到的有序性，将它们有序地合并在一个工作区，最后用工作区中排好序的全序列更新原待排序的元素序列成为所要求的排好序的元素序列。 6.3 合并排序算法(非就地) 6.3.1 递归版的合并排序算法 (2)算法的实现 6.3 合并排序算法(非就地) 6.3.1 递归版的合并排序算法 算法的复杂度 显然,Copy可在O(n)时间内完成。也容易理解，Merge可在O(n)时 间内完成。因此合并排序算法对n个元素进行排序，在最坏情况 下所需的计算时间T(n)满足 解此递归方程可知T(n)=O(nlogn)。 由于基于比较的排序问题的计算时间下界为Ω(nlogn)，故合并 排序算法是一个渐近最优算法。 但它需要加倍的空间,即需要O(n)的辅助空间。 6.3 合并排序算法(非就地) 6.3.2 非递归版的合并排序算法 (1)基本思想 事实上， 算法MergeSort的递归过程只是将待排序数组一分为二，直至待排序数组中只有