选择和基数排序讲述.ppt

选择排序和基数排序 选择排序的基本思想 简单选择排序 堆选择排序 小结和作业 基数排序 选择排序的基本思想 选择排序的基本思想： 每一趟从待排序的n-i+1（i=1,2,3,…,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。 1. 直接选择排序 2. 堆选择排序 简单选择排序-基本思想 假设排序过程中，待排记录序列的状态为： 有序序列R[1..i-1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列R[1..i] 无序序列 R[i+1..n] 简单选择排序-基本思想 第i趟排序过程： 1）第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]； 2）该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换 3）使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少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 97 13 65 97 76 97 97 排序结果： 27 38 38 49 76 65 97 简单选择排序-算法 void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; in; ++i) {//排序的趟数 } } // SelectSort k= SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=k) R[i]←→R[k]; // 与第 i 个记录交换 简单选择排序-性能分析 1.对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为： 2.移动记录的次数，当待排序列为正序数为最小，最小值为 0。 3.简单选择排序是一种不稳定的排序方法 ??? 待排序列为逆序数为最大，最大值为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 与r[1]交换位置 交换，不稳定的 简单选择排序-讨论 例：关键字序列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，38，11，9） 小顶堆 大顶堆 堆的定义 堆是满足下列性质的数列{r1, r2, …，rn}： 或 (小顶堆) (大顶堆) 若将此序列所存储的一维数组R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树： 树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 堆的定义 小顶堆：??? 　根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。 大顶堆：??? 　根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。 注意：??? 　①堆中任一子树亦是堆。???　 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 堆排