计算机软件基础之数据结构-排序初步.ppt

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（log2n），最坏的空间复杂度为O(n)。 　　快速排序是一种不稳定的排序方法。 　选择排序 　直接选择排序 1、直接选择排序的基本思想 　　直接选择排序（straight select sorting）也是一种简单的排序方法。它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，第三次从R[2]~R[n-1]中选取最小值，与R[2]交换，…，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…, 第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 　　例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图5所示。 3、直接选择排序的效率分析 　　在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行n-i次比较（1≤i≤n-1），而每次交换最多需3次移动，因此，总的比较次数C= 　 =(n2-n)/2，总的移动次数M= =3(n-1)。由此可知，直接选择排序的时间复杂度为O(n2)数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。　　 　　由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。例如，给定排序码为3，7，3，2，1，排序后的结果为1，2，3，3，7。 　堆排序 1、堆的定义 　　若有n个元素的排序码k1，k2，k3，…，kn，当满足如下条件： ki≤k2i ki≥k2i （1）ki≤k2i+1 或 (2) ki≥k2i+1 其中i=1,2,…,?n/2? 　　 　　则称此n个元素的排序码k1，k2，k3，…，kn为一个堆。 　　若将此排序码按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。 　　若n个元素的排序码k1，k2，k3，…，kn满足堆，且让结点按1、2、3、…、n顺序编号，根据完全二叉树的性质（若i为根结点，则左孩子为2i，右孩子为2i+1）可知，堆排序实际与一棵完全二叉树有关。若将排序码初始序列组成一棵完全二叉树，则堆排序可以包含建立初始堆（使排序码变成能符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。 2、堆排序的基本思想 　　将排序码k1，k2，k3，…，kn表示成一棵完全二叉树，然后从第?n/2? 个排序码开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第?n/2? -1个排序码重复刚才操作，直到第一个排序码止。这时候，该二叉树符合堆的定义，初始堆已经建立。