数据结构-快速和堆排序ppt课件.ppt

《数据结构-快速和堆排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、交换类排序和选择类排序起泡排序快速排序小结和作业交换类排序选择排序的基本思想简单选择排序堆选择排序基数排序交换类排序交换排序的基本思想：依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序。主要应用：1）起泡排序(BubbleSort)2）快速排序(QuickSort)起泡排序假设在排序过程中，记录序列R[1..n]的状态为：第i趟起泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上起泡排序30

2、65977613273801234567494938jj+19776971397279730jj+1jj+1jj+1jj+1jj+1jj+1第一趟起泡排序过程976576132730490123456738第一趟起泡排序后的结果起泡排序97657613273049012345673897657613273049012345673813762776307676第二趟976513273030490123456738136565307676第三趟276565971327303030490123456738494949307676第四趟65651349

3、27起泡排序971327303030490123456738494949307676第四趟65651349279727301301234567384976第五趟65133827383830389730302701234567134976第六趟65383830起泡排序1.每一趟起泡排序都是将待排序序列中最大的关键字移动到最后一个记录的位置上。2.起泡排序的结束条件为，最后一趟没有进行“交换记录”。3.一般情况下，每经过一趟“起泡”，“i减一”，但并不是每趟都如此。起泡排序例如:2553157989i=7i=613i=2起泡排序voidBubble

4、Sort(ElemR[],intn){i=n;//从1…i中找最大的，结果放到iwhile(i>1){lastExchangeIndex=1;for(j=1;j

5、列中顺序有序）：只需进行一趟起泡关键字在记录序列中逆序有序）：需进行n-1趟起泡O(n2)时间复杂度：稳定性：是一种稳定的排序方法n-1快速排序-基本思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。快速排序-基本思想首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。1436525861492397807501234567891052枢轴再进行快速排序再进行快速排序快速排序-划分目标：找一个记

6、录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)枢轴(i+1≤j≤t)。快速排序-划分80361458614952972375012345678910stR[0]=52lowhighhigh23lowlow80highhigh14lowlow52highhigh一趟快速排序过程：快速排序-划分1.(初

7、始化)设置两个指针low和high，它们的初值分别为区间的下界和上界；2.选取无序区的第一个记录R[low].key作为基准记录，并将它保存在变量pivotkey中；3.令high起向左扫描，直到找到第1个关键字小于pivotkey的记录R[high]，将R[high])移至low所指的位置上，这相当于R[high].key和基准R[0].key(即pivotkey)进行了交换，使关键字小于基准关键字pivotkey的记录移到了基准的左边，交换后R[high]中相当于是pivotkey；快速排序-划分4.然后，令low指针自low+1位置开始向

8、右扫描，直至找到第1个关键字大于pivotkey的记录R[low]，将R[low]移到high所指的位置上，这相当于交换了R[low]和基准R[hig