第7单元排序主讲：刘志强

第7单元排序主讲：刘志强内容摘要：

} 示例 下一页 上一页 停止放映 第 29 页 改进的冒泡排序算法 38  从上述举例中可以看出 ， 从第 4趟冒泡起 ， 序列已有序 ， 结果是空跑了 3趟。 若两次冒泡处理过程中 ， 没有进行交换 ， 说明序列已有序 ， 则停止交换。 这就是改进的冒泡算法的处理思想。  用改进的冒泡算法处理 ， 比较次数有所减少。 对于数列 { 65,97,76,13,27,49,58 } 比较次数 第 1趟 {65， 76， 13， 27， 49， 58}， {97} 6 第 2趟 {65， 13， 27， 49， 58}， {76， 97} 5 第 3趟 {13， 27， 49， 58}， {65， 76， 97} 4 第 4趟 {13， 27， 49}， {58， 65， 76， 97} 3 总计： 18 次 下一页 上一页 停止放映 第 30 页 改进的冒泡排序算法 38 bubble_a(int *item,int count) { int a,b,t,c。 for(a=1。 acount。 ++a) /* n1趟的循环 */ { c=1。 /* 设置交换标志 */ for(b=1。 b=counta。 b++)/* n1趟处理 */ { if(item[b1]item[b])/* 若逆序 ， 则 */ { t=item[b1]。 /* 交换位置 */ item[b1]=item[b]。 item[b]=t。 c=0。 } /* 若有交换 ， 则 */ } /* 改变交换标志 */ if(c) break。 /* 若没有交换 ， 则 */ } /* 退出处理 */ } 示例 下一页 上一页 停止放映 第 31 页 算法讨论 若待排序列有序 (递增或递减 ),则只需进行一趟冒泡处理即可。 若反序，则需进行 n1趟的冒泡处理。 在最坏的情况下 ,冒泡算法的时间复杂度是O( n2 )。 当待排序列基本有序时，采用冒泡排序法效果较好。 冒泡排序算法是稳定的。 下一页 上一页 停止放映 第 32 页 快速排序 快速排序法是一位计算机科学家。 曾被认为是最好的一种排序方法。 快速排序法是对冒泡排序法的一种改进 ，也是基于交换排序的一种算法。 因此 ， 被称为 “ 分区交换排序 ”。 下一页 上一页 停止放映 第 33 页 快速排序基本思想  在待排序序列中按某种方法选取一个元素 K， 以它为分界点 ， 用交换的方法将序列分为两个部分：比该值小的放在左边 ， 否则在右边。 形成 {左子序列 }K{右子序列 } 再分别对左 、 右两部分实施上述分解过程 ， 直到各子序列长度为 1， 即有序为止。  分界点元素值 K的选取方法不同 ， 将构成不同的排序法 ，也将影响排序的效率： – 取左边第 1个元素为分界点； – 取中点 A[（ left+right） /2]为分界点； – 选取最大和最小值的平均值为分界点等。  设有序列 {a1， a2， … ,An},选取中点元素 K为分界点 ,分别从序列两头分别与 K进行比较 ,小于 K的元素交换到左边 ,否则交换到右边。 一趟处理后 ,左边子序列的元素均小于分界点值 K,右边子序列元素均大于等于 K值。 下一页 上一页 停止放映 第 34 页 快速排序（算法 39） Step1 分别从两端开始 ， 指针 i指向第一个元素A[left]， 指针 j指向最后一个元素 A[right]，分界点取 K ； Step2 循环 （ ij） 从右边开始进行比较： 若 K  A[j]， 则将 A[j]交换到左边； 若 K 〈 A[j] ， 则 j=j1， 再进行比较； 从左边开始进行比较： 若 K 〉 A[i]， 则 i=i+1， 再进行比较； 若 K  A[i]， 则将 A[i]交换到右边。 当 ij时 ， 一次分解操作完成。 Step3 在对分解出的左 、 右两个子序列按上述步骤继续进行分解 ， 直到子序列长度为 1（ 不可再分 ） 为止 ， 也即序列全部有序。 下一页 上一页 停止放映 第 35 页 快速排序算法举例 对于数列 {49， 38， 60， 90， 70， 15， 30， 49}， 采用中点分界法： 初始状态 : 49 38 60 90 70 15 30 49 比较次数 第 1趟 49 38 60 90 70 15 30 49 49 38 60 90 70 15 30 49 5（ i j1） 49 38 30 49 70 15 60 90 5（ i j1） { 49 38 30 49 70 15 60 } 90 小计： 10 i k = 90 j i j j i 下一页 上一页 停止放映 第 36 页 快速排序算法举例（续一） 初始状态 : 49 38 60 49 70 15 30 比较次数 第 2趟 49 38 60 49 70 15 30 2（ i j1） 30 38 60 49 70 15 49 30 38 60 49 70 15 49 30 38 15 49 70 60 49 { 30 38 15}49{ 70 60 49 } 小计： 8 i j k = 49 j i i j 3（ i j1） i j 3（ i j2） 下一页 上一页 停止放映 第 37 页 快速排序算法举例（续二） 初始状态 : 30 38 15 比较次数 第 3趟 30 38 15 3（ i j1） { 30， 15 } 38 小计： 3 第 4趟 70 60 49 2（ i j1）。