26 快速排序和选择排序1 - 副本.ppt

《26 快速排序和选择排序1 - 副本.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10章内部排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较10.3交换排序1.起泡排序2.快速排序1）起泡排序的基本思想小的浮起，大的沉底具体做法：第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，…关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；依次类推，则完成排序。1.起泡排序362511第六趟36412511第五趟3641491125第四趟4

2、13656114925第三趟65364111564925第二趟1136416578495625第一趟1136416578495625初始状态起泡排序示例495611787865784178365611654165364911564156362511494149364136voidBubblesort(ElemTypeR[],intn){intflag=1;//当flag为0则停止排序for(inti=n;i>1;i--){//i表示趟数，最多n-1趟flag=0;//开始时元素未交换for(intj=2;j<=i;j++)

3、if(R[j]

4、排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。1）基本思想通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。通常取第一个记录的值为基准值或枢轴。2）具体做法附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key；(1)从high所指位置起向前搜索，找到第一个不大于基准值的记录

5、与枢轴记录相互交换；(2)从low所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。(3)重复这两步直至low=high为止。21（210337139109）lowhigh枢轴21（090313219137）21（0903139137）lowhigh枢轴21high枢轴（210337139109）low0921（0903371391）low枢轴high37lowhighlow133）一趟快速排序算法描述intPartition(ElemR[],intlow,inthigh){R[0]=R[low];piv

6、otkey=R[low].key;while(low=pivotkey)--high;R[low]=R[high];//将比枢轴记录小的移到低端while(low

7、排序算法voidQSort(ElemR[],intlow,inthigh){if(low

8、右子区间的长度大致相等）,快速排序的最好时间复杂度应为O(nlog2n)。最坏的情形（每次能划分成两个子区间，但其中一个是空），快速排序的最坏时间复杂度为O(n2)。对n较大的情况，它是平均速度最快的排序算法，但当n很小时，此方法往往比其他简单排序方法还要慢。快速排序是不稳定的。第10章内部排序10.1