《数据结构-快速和堆排序》由会员分享，可在线阅读，更多相关《数据结构-快速和堆排序（72页珍藏版）》请在金锄头文库上搜索。
1、交换类排序和选择类排序,起泡排序,快速排序,小结和作业,交换类排序,选择排序的基本思想,简单选择排序,堆选择排序,基数排序,交换类排序,交换排序的基本思想： 依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序。,主要应用： 1）起泡排序(Bubble Sort) 2）快速排序 (Quick Sort),起泡排序,假设在排序过程中，记录序列R1n的状态为：,第 i 趟起泡排序,无序序列R1n-i+1,有序序列 Rn-i+2n,n-i+1,无序序列R1n-i,有序序列 Rn-i+1n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,起泡排序,30,65,97,76,1
2、3,27,38,49,49,38,97,76,97,13,97,27,97,30,第一趟起泡排序过程,97,65,76,13,27,30,49,38,第一趟起泡排序后的结果,起泡排序,97,65,76,13,27,30,49,38,97,65,76,13,27,30,49,38,13,76,27,76,30,76,76,第二趟,97,65,13,27,30,30,49,38,13,65,65,30,76,76,第三趟,27,65,65,97,13,27,30,30,30,49,38,49,49,49,30,76,76,第四趟,65,65,13,49,27,起泡排序,97,13,27,30,30
3、,30,49,38,49,49,49,30,76,76,第四趟,65,65,13,49,27,97,27,30,13,38,49,76,第五趟,65,13,38,27,38,38,30,38,97,30,30,27,13,49,76,第六趟,65,38,38,30,起泡排序,1. 每一趟起泡排序都是将待排序序列中最大的关键字移动到最后一个记录的位置上。,2. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。,3. 一般情况下，每经过一趟“起泡”，“i减一”，但并不是每趟都如此。,起泡排序,例如:,2,5,5,3,1,5,7,9,8,9,i=7,i=6,1,3,i=2,起泡排序,void
4、BubbleSort(Elem R , int n) i = n;/从1i中找最大的，结果放到i while (i 1) lastExchangeIndex = 1; for (j = 1; j i; j+)/每趟需要比较的元素对的个数 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /进行交换的记录位置 /if i = lastExchangeIndex; / 本趟进行过交换的 / 最后一个记录的位置 / while / BubbleSort,起泡排序-性能分析,0,关键字在记录序列中顺序有序）：只需进行一趟起泡,关键字
5、在记录序列中逆序有序）：需进行n-1趟起泡,O(n2),时间复杂度：,稳定性：,是一种稳定的排序方法,n-1,快速排序-基本思想,快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conquer Method)。,快速排序-基本思想,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,14,36,52,58,61,49,23,97,80,75,52,枢轴,再进行快速排序,再进行快速排序,快速排序-划分,目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动
6、至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。,致使一趟排序之后，记录的无序序列Rst将分割成两部分：Rsi-1和Ri+1t，且 Rj.key Ri.key Rj.key (sji-1) 枢轴 (i+1jt)。,快速排序-划分,80,36,14,58,61,49,52,97,23,75,s,t,R0=,52,23,80,14,52,一趟快速排序过程：,快速排序-划分,1. (初始化)设置两个指针low和high ，它们的初值分别为区间的下界和上界； 2. 选取无序区的第一个记录Rlow.key作为基准记录，并将它保存在变量pivotkey中；,3. 令high起向左扫描，直到找
7、到第1个关键字小于pivotkey的记录Rhigh，将Rhigh)移至low所指的位置上，这相当于Rhigh.key和基准R0.key(即pivotkey)进行了交换，使关键字小于基准关键字pivotkey的记录移到了基准的左边，交换后Rhigh中相当于是pivotkey ；,快速排序-划分,4. 然后，令low指针自low+1位置开始向右扫描，直至找到第1个关键字大于pivotkey的记录Rlow，将Rlow移到high所指的位置上，这相当于交换了Rlow和基准Rhigh，使关键字大于基准关键字的记录移到了基准的右边，交换后Rlow中又相当于存放了pivotkey,5. 接着令指针high自
8、位置high-1开始向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至low=high时，low便是基准pivotkey最终的位置，将pivotkey放在此位置上就完成了一次划分。,快速排序-划分练习,38,65,97,76,13,27,49,快速排序-划分,int Partition (RedType R, int low, int high) / Partition,R0 = Rlow; /枢轴pivotkey = Rlow.key;,while (lowhigh) ,while(low=R0) - high; / 从右向左搜索,Rlow = Rhigh;,while (lowhi
9、gh / 从左向右搜索,Rhigh = Rlow;,Rlow = R0; return low;,快速排序-算法,void QSort (RedType & R, int s, int t ) / 对记录序列Rst进行快速排序 if (s t) / 长度大于1 / QSort,pivotloc = Partition(R, s, t); / 对 Rst 进行一次划分,QSort(R, s, pivotloc-1); / 对低子序列递归排序，pivotloc是枢轴位置,QSort(R, pivotloc+1, t); / 对高子序列递归排序,快速排序-算法,void QuickSort( SqL
10、ist / QuickSort,第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。,快速排序-性能分析,假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间：,其中 Tpass(n)为对 n 个记录进行一次划分所需时间，和记录数n成正比，可用cn表示。,T(n) = Tpass(n) + T(k-1) + T(n-k),若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。,快速排序-性能分析,设 Tavg(1)b,则可得结果：,结论: 在所有同数量级O(nlogn)的排序方 法中快速排序平均性能最好。,由此可
11、得快速排序所需时间的平均值为：,快速排序-性能分析,若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。为避免出现这种情况，需在进行一次划分之前，进行“予处理” ：,先对 R(s).key, R(t).key 和 R(s+t)/2.key，进行相互比较，然后取关键字为 “三者之中”的记录为枢轴记录。,或者，随机取一个作为枢轴,快速排序-性能分析,快速排序是一种不稳定的排序方法。,快速排序需要的辅助存储空间为：,R0,执行栈 ,栈的大小？,如果每次先对 短的区间进行快速排序，则,2log2n,选择排序的基本思想,选择排序的基本思想：,每一趟从待排序的n-i+
12、1（i=1,2,3,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。,1. 直接选择排序,2. 堆选择排序,简单选择排序-基本思想,假设排序过程中，待排记录序列的状态为：,有序序列R1i-1,无序序列 Rin,第 i 趟 简单选择排序,从中选出 关键字最小的记录,有序序列R1i,无序序列 Ri+1n,简单选择排序-基本思想,第i趟排序过程： 1）第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin； 2）该趟排序从当前无序区中选出关键字最小的记录Rk，将它与无序区的第i个记录Ri交换 3）使R1i和Ri+1n分别变为记录个数增加1个的新有序区和记录
13、个数减少1个的新无序区,49,13,简单选择排序-例子,65,97,76,13,27,38,49,第一趟 i=1,13,13,简单选择排序-例子,65,97,76,49,27,38,第二趟： i=2,27,38,27,13,简单选择排序-例子,65,97,76,49,38,第三趟： i=3,27,65,38,38,13,65,97,76,49,65,第四趟： i=4,27,38,97,49,49,简单选择排序-例子,13,65,97,76,97,65,第五趟： i=5,27,38,38,49,76,65,13,65,97,76,97,76,第六趟： i=6,27,38,38,49,76,65,
14、97,13,65,97,76,97,97,排序结果：,27,38,38,49,76,65,97,简单选择排序-算法,void SelectSort (Elem R, int n ) / 对记录序列R1n作简单选择排序。 for (i=1; in; +i) /排序的趟数 / SelectSort,k= SelectMinKey(R, i); / 在 Rin 中选择关键字最小的记录,if (i!=k) RiRk; / 与第 i 个记录交换,简单选择排序-性能分析,1.对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：,2.移动记录的次数，当待排序列为正序数为最小，最小值为 0。,3.
15、简单选择排序是一种不稳定的排序方法 ?,待排序列为逆序数为最大，最大值为3(n-1) 。,简单选择排序-讨论,例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。,原始序列： 21，25，49，25*，16，08,第1趟 第2趟 第3趟 第4趟 第5趟,08，25，49，25*，16，21 08，16, 49，25*，25，21 08，16, 21，25*，25，49 08，16, 21，25*，25，49 08，16, 21，25*，25，49,最小值 08 与r1交换位置,交换，不稳定的,简单选择排序-讨论,例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。,原始序列： 21，25，49，25*，16，08,第1趟 第2趟 第3趟 第4趟 第5趟,08，21，25，49，25*，16 08，16, 21，25，49， 25* 08，16, 21，25, 49, 25* 08，16, 21，25， 49, 25* 08，16, 21，25, 25*，49,移动，稳定的,堆的定义,（13，38，27，50，76，65，49，97）,（96，83，27，
