软件工程与c语言chapter46课件.pptVIP

4.6.2 快速排序 一. 基本思想 任取待排序序列中的某个元素作为基准（一般取第一个元素），将待排序元素分为左右两个子表，左子表中元素的关键字值均小于或等于基准元素的关键字值，右子表中元素的关键字值均大于或等于基准元素的关键字值，然后分别对两个子表继续进行划分，直至每一个子表只有一个元素或为空为止。最后得到的便是有序序列。 概括地说： 一次划分就是从表的两端交替方向地向中间进行扫描, 将小的放到左边, 大的放到右边, 作为基准的元素放到中间。 快速排序一次划分过程 1． i指向待划分区域最左端，j指向待划分区域最右端; 2. 保存基准元素的值，r[0]=r[i] ; 3.? ?从右向左扫描(首先开始此方向的扫描) j从右向左移动，直到r[j].keyr[0].key或i==j; 4.? 若 r[j].keyr[0].key ，则r[i]=r[j], i=i+1，改变扫描方向； 5.? ?从左向右扫描： i从左向右移动，直到r[i].keyr[0].key或i==j; 6.?? 若r[i].keyr[0].key，则 r[j]=r[i], j=j-1，改变扫描方向; 7. 重复3~6，直到i,j位置重合（即i==j），此位置即最终的划分位置； 8. ?将基准元素放入最终的划分位置，r[i]=r[0]或r[j]=r[0] 一次划分过程演示 一次划分过程演示 一次划分过程演示 一次划分过程演示 一次划分过程演示 一次划分过程演示 实现一次划分的算法： int Partition(list r[],int i,int j) { r[0]=r[i];　/* 暂存基准元素到r[0]中*/ while(ij) /* 从表的两端交替地向中间扫描 */ {while(ijr[j].key=r[0].key) 　 j--; if(ij) { r[i]=r[j];　i++;　} while(ijr[i].key=r[0].key) 　 i++; 　 if (ij) { r[j]=r[i]; j--; } } r[i]=r[0]; /* 将基准元素放到其最终位置 */ return i; 　/* 返回基准元素所在的位置*/ } 递归算法分析 递归退出的条件： 数据表为空或数据表中只有一个元素。 即: low≥high。 快速排序的递归过程 递归算法 void QSort(list r[],int low,int high)　 {/*对r[low]到r[high]范围内的元素进行快速排序*/ int mid; { if (lowhigh) { mid=Partition(r,low,high); QSort(r,low,mid-1); QSort(r,mid+1,high);} } } 下面的快速排序算法实现将一个长度为n的线性表r上的所有元素按关键字升序排列。 void Quick_Sort(list r[],int n)　 { QSort(r,1,n); } 算法分析 4 3 3 快速排序的递归树 思考题 “三者取中”的规则　 “ 三者取中” 规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区间的第 1 个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。 课后练习题 1．假如待排序的关键字序列为{1，2，3，4，5，6，7}，请问初始状态为什么时，快速排序效率最高？ 2．给定一组关键字序列{19，26，92，87，11，43，87，21}，用快速排序方法进行升序排列，写出每趟排序后关键字的排列情况。 * * 怎样具体实现？ 快速排序一次划分过程 38 20 46 38 74 91 12 思考：怎样为38找位置，正确地实现表的一次划分？ 为了减少数据的移动,将作为基准的元素暂存到r[0]中，最后再放入最终位置 2． r[0]=r[i] i 12 91 74 38 46 20 38 j 0 1 2 3 4 5