26 快速排序和选择排序1.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * 第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.起泡排序 36 25 11 第 六 趟 36 41 25 11 第 五 趟 36 41 49 11 25 第 四 趟 41 36 56 11 49 25 第 三 趟 65 36 41 11 56 49 25 第 二 趟 11 36 41 65 78 49 56 25 第 一 趟 11 36 41 65 78 49 56 25 初 始 状 态 起 泡 排 序 示 例 49 56 11 78 78 65 78 41 78 36 56 11 65 41 65 36 49 11 56 41 56 36 25 11 49 41 49 36 41 36 void Bubblesort(ElemType R[],int n) { int flag=1; //当flag为0则停止排序 for (int i=n; i1; i--) { //i表示趟数，最多n-1趟 flag=0; //开始时元素未交换 for (int j=2; j=i; j++) if (R[j]R[j-1]) { //发生逆序 temp=R[j]; R[j]=R[j-1]; R[j-1]=temp; flag=1; } if(flag==0) return; } } // Bubblesort 2）起泡排序算法描述 正序： 只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；时间复杂度为O(n) 。 逆序： 需要进行n-1趟排序，需要进行n(n-1)/2次比较，并作等数量级的记录移动。总的时间复杂度为O(n2) 。 起泡排序方法是稳定的。适合于数据较少的情况。 3）起泡排序算法分析 2.快速排序 背景 起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小 1。 试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。 1）基本思想 通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。 通常取第一个记录的值为基准值或枢轴。 2）具体做法 附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为 key； (1)从high 所指位置起向前有哪些信誉好的足球投注网站，找到第一个不大于基准值的记录与枢轴记录相互交换； (2)从low 所指位置起向后有哪些信誉好的足球投注网站，找到第一个不小于基准值的记录与枢轴记录相互交换。 (3)重复这两步直至low=high为止。 21 （ 21 03 37 13 91 09 ） low high 枢轴 21 （ 09 03 13 21 91 37 ） 21 （ 09 03 13 91 37 ） low high 枢轴 21 high 枢轴 （ 21 03 37 13 91 09 ） low 09 21 （ 09 03 37 13 91 ） low 枢轴 high 37 low high low 13 3）一趟快速排序算法描述 int Partition (Elem R[ ], int low, int high){ R[0] = R[low]; pivotkey = R[low].key; while (low high) { //从两端交替向中间扫描 while (low high R[high].key = pivot