(湖大公考)湖南省农村信用社考试之数据结构课件分析.ppt

例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图7-3给出冒泡排序算法的执行过程。 冒泡排序的效率分析 比较次数： 最少：n-1次 好序 最多：n*(n-1)/2 逆序 移动次数： 最少：0次 好序 最多：3n*(n-1)/2 逆序 因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。适合于对基本好序的数组进行排序 冒泡排序算法是一个稳定的算法。 1．快速排序的基本思想 快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行快速排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。 快速排序 例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。 一次分划图示(1) 46 55 13 42 94 05 17 70 Low high 46 55 13 42 94 05 17 70 Low high 17 55 13 42 94 05 46 70 Low high 一次分划图示(2) 17 05 13 42 94 46 55 70 Low high 17 46 13 42 94 05 55 70 Low high 17 05 13 42 46 94 55 70 Low high 3．快速排序的效率分析 若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1 ，所以总的比较次数不会超过(n+1) log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1≤i≤n）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。 快速排序是一种不稳定的排序方法。 直接选择排序 直接选择排序也是一种简单的排序方法。它的基本思想是：用逐个比较的方法第一次从array[1]~array[n]中选取最小值，与array[1]交换，第二次从array[2]~array[n]中选取最小值，与array[2]交换，第三次从array[3]~array[n]中选取最小值，与array[3]交换，…，第i次从array[i]~array[n]中选取最小值，与array[i]交换，…, 第n-1次从array[n-1]~array[n]中选取最小值，与array[n-1]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 选择排序 例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。 初始状态 8 3 2 1 7 4 6 5 第 一 次 1 3 2 8 7 4 6 5 第 二 次 1 2 3 8 7 4 6 5 第 三 次 1 2 3 8 7 4 6 5 第 四 次 1 2 3 4 7 8 6 5 第 五 次 1 2 3 4 5 8 6 7 第 六 次 1 2 3 4 5 6 8 7 第 七 次 1 2 3 4 5 6 7 8 Void SelectSort(SqList L){ for