数据结构chapter 10(2)堆排序算法

《数据结构chapter 10(2)堆排序算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DATASTRUCTURE,DS授课教师：郭艳授课班级:191091:191091-4中国地质大学计算机学院2011年春上堂课要点回顾¢排序¢排序的定义和类型¢排序算法的衡量标准¢排序算法¢直接插入排序¢直接选择排序¢冒泡排序¢希尔排序¢堆排序第十九次课阅读：朱战立，第266-275页习题：作业17数据结构课程内容⎧直接插入排序⎪⎪直接选择排序⎪冒泡排序⎪⎪希尔排序⎨⎪堆排序⎪快速排序⎪⎪归并排序⎪⎩基数排序堆排序算法¢先建初始最大堆¢对n个结点产生堆的过程是从i=⎣n/2−1⎦开始到0，反复调用筛选算法，

2、每次将x[i]~x[n-1]建成最大堆，最后将x[0]~x[n-1]建成初始最大堆¢进行n-1趟堆排序¢设i表示趟数，从n-1到0，每趟¢交换堆顶记录x[0]与当前未排序子序列的最后一个记录x[i]，x[0]定位在正确位置¢重新调整，把x[0]“拉下来”，使记录x[0]~x[i-1]成为最大堆【堆排序算法】voidHeapSort(DataTypex[],intn)/*用堆排序法对记录x[0]~x[n-1]排序*/{inti;/*将x[0]~x[n-1]建成初始的最大堆*/for(i=n/2-1;i>=0;i--)

3、HeapAdjust(x,n,i);for(i=n-1;i>0;i--){/*交换堆顶记录与当前未排序子序列的最后一个记录x[i]的位置*/swap(x,0,i);/*重新调整，把x[0]“拉下来”，使记录x[0]~x[i-1]成为最大堆*/HeapAdjust(x,i,0);}}堆排序算法分析¢不稳定排序算法¢总时间代价为O(nlog2n)¢一次建堆，n次删除堆顶并重新调整¢建堆：O(n)¢删除堆顶并重新调整为堆:O(log2n)¢空间代价为O(1)10.4.2快速排序¢算法思想：¢选择轴值（pivot）¢将序列

4、划分为两个子序列L和R，使得L中的所有记录都小于或等于轴值，R中的所有记录都大于轴值，即轴值已经定位在正确位置LR¢对子序列L和R递归进行快速排序轴值选择（SelectPivot）¢尽可能使L和R的长度相等¢选择策略：¢选择最左边的记录¢选择中间记录，须将中间记录和最左边记录互换¢选择平均值，须将平均值的记录和最左边记录互换（可使L和R的长度相等）¢随机选择，须将选择的记录和最左边记录互换划分过程（Partition）¢划分是整个快速排序的关键¢划分后使得L中所有记录位于轴值左边，R中记录位于轴值右边，即轴值已经定

5、位于正确位置LRtemp.key例：初始关键字：[465513429451770]ijj进行一次交换后：[17]55134294517[70]ij进行二次交换后：[17]551342945[5570]ij进行三次交换后：[175]1342945[5570]iiij进行四次交换后：[1751342]94[945570]ij完成一趟排序：[1751342]46[945570]二趟排序之后：[135]17[42]46[7055]94三趟排序之后：[5]13174246[55]7094【快速排序的轴值选择函数】intSel

6、ectPivot(intlow,inthigh){/*参数lhlow,hiihgh分别表示待排序序列的左右端下标*///选择最左记录作为轴值returnlow;}【快速排序的分割函数】intPartition(DataTypex[],intlow,inthigh){//分割后轴值已到达正确位置DataTypetemp;//存放轴值的临时变量itilinti=low;//i//i为左指针，j为右指针intj=high;//将轴值存放在临时变量中temp=x[i];//开始分割，iji,j不断向中间移动，直到相遇whi

7、le(ithile(x[j].key>temp.k)&&(i

8、];j--;//j指针向左移动一步}}//把轴值回填到分界位置i上x[[]i]=temp;p;returni;//返回分界位置i}【快速排序算法】voidQuickSortQuick_Sort(DataTypex[],intlow,inthigh)/*对记录x[low]~x[high]作快速排序（递归算法）*/{itintijiti,j,pivot;if(h