10 第10章 排序.ppt

注意从后面往前面比。 　　3、冒泡排序的效率分析 　　从上面的例子可以看出，当进行完第三趟排序时，数组已经有序，所以第四趟排序的交换标志为0，即没进行交换，所以不必进行第四趟排序。 　　从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。 　　因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。 9.3.2　快速排序 1、快速排序的基本思想 　　快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。 　　它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。 　　快速排序的过程为：把待排序区间按照第一个元素（即基准元素）的排序码分为左右两个子序列的过程叫做一次划分。设待排序序列为R[left]～R[right]，其中left为下限，right为上限，left＜right，R[left]为该序列的基准元素，为了实现一次划分，令i,j的初值分别为left和right。在划分过程中，首先让j从它的初值开始，依次向前取值，并将每一元素R[j]的排序码同R[left]的排序码进行比较，直到R[j]R[left]时，交换R[j]与R[left]的值，使排序码相对较小的元素交换到左子序列，然后让i从i＋1开始，依次向后取值，并使每一元素R[i]的排序码同R[j]的排序码（此时R[j]为基准元素）进行比较，直到R[i]＞R[j]时，交换R[i]与R[j]的值，使排序码大的元素交换到后面子区间；再接着让j从j-1开始，依次向前取值，重复上述过程，直到i等于j,即指向同一位置为止，此位置就是基准元素最终被存放的位置。此次划分得到的前后两个待排序的子序列分别为R[left]～R[i-1]和R[i+1]～R[right]。 　　例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图9-4所示。 　　从图9-4可知，通过一次划分，将一个区间以基准值分成两个子区间，左子区间的值小于等于基准值，右子区间的值大于基准值。对剩下的子区间重复此划分步骤，则可以得到快速排序的结果。 　　2、快速排序的算法实现 　　下面给出快速排序算法的递归算法如下： void quicksort(ElemType R[],int left , int right) { int i=left , j=right; ElemType temp=R[i]; while (ij) { while ((R[j]temp)(ji)) j=j-1; if (ji) { R[i]=R[j]; i=i+1; } while ((R[i]=temp)(ji)) i=i+1; if (ij) { R[j]=R[i]; j=j-1; } } //一次划分得到基准值的正确位置 R[i]=temp; if (lefti-1) quicksort(R,left,i-1); //递归调用左子区间 if (i+1right) quicksort(R,i+1,right); }//递归调用右子区间 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（