数据结构之树和图算法课件.pptVIP

各种内排序方法的选择 1．从时间复杂度选择 对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。 2．从空间复杂度选择 尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。 3．一般选择规则 （1） 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。 （2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。 （3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。 （4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。 (5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。 各种排序方法的比较 案例分析：多项式相加 C++中如何表示多项式 链表 对两个多项式中的每个数据项的变量进行排序 执行加法运算 课堂练习 对于一组记录的排序码为(465，792，562，383，401，845，502，423)，写出基数排序（低位优先）进行一趟分配与回收后的结果。 序列 8 , 3 , 10 , 13 , 25 , 18 , 6 , 4 对上述序列使用直接插入排序、希尔排序（d1=4；d2=2;d3=1;）、快速排序、堆排序、归并排序、基数排序（低位优先）进行排序的过程。 作业1 作业2 P409：1，15 上机作业 直接插入排序程序 希尔排序程序 编写冒泡排序程序（改进版） 快速排序程序 简单选择排序程序 归并排序程序 思想: 每一趟都选出一个最大或最小的元素，并放在合适当的位置。 简单选择排序 树形选择排序 堆排序 选择排序 思想: 第 1 趟选择: 从 1—n 个记录中选择关键字最小的记录，并和第 1 个记录交换。 第 2 趟选择: 从 2—n 个记录中选择关键字最小的记录，并和第 2 个记录交换。 第n-1趟选择: 从 n-1—n 个记录中选择关键字最小的记录，并和第 n-1 个记录交换。 . . . 简单选择排序 例，序列 49 38 97 65 76 第 1 趟选择: min 38 49 97 65 76 第 2 趟选择: min 38 49 97 65 76 第 3 趟选择: min 38 49 65 97 76 第 4 趟选择: min 38 49 65 76 97 直接选择排序的算法 template class T void SelectSort ( T Vector[], int CurrentSize) { for ( int i = 0; i CurrentSize-1; i++ ) { int k = i; //选择具有最小排序码的对象 for ( int j = i+1; j CurrentSize; j++) if ( Vector[j] Vector[k] ) k = j; //当前具最小排序码的对象 if ( k != i ) //对换到第 i 个位置 Swap ( Vector[i], Vector[k] ); } } 选择排序的主要操作是进行关键字间的比较。 在 n 个关键字中选出最小值，至少需要 n-1 次比较。 在剩余的 n-1 个关键字中选出最小值，至少需要 n-2 次比较？ 如果能利用前 n-1 次比较所得信息，可以减少后面选择的比较次数。 体育比赛中的锦标赛: 例，8 名运动员要决出 冠、亚、季军。 按简单选择排序需要比赛 7+6+5 = 18 场。 若能够利用以前的比赛结果，比赛场次实际可以减少为 11 场。 前提: 若 甲 胜 乙 ，乙 胜 丙 ，则 甲 必能胜 丙 。 Zhao Cha Liu Bao Diao Yang Xue Wang Bao Bao Diao Cha Bao Diao Wang 冠军 如何求 亚军？ Zhao Cha Liu Diao Yang Xue Wang Cha Diao Cha 亚军 可以利用前面的比赛结果！ Cha Liu Diao Wang 如何求 季军？ Zhao Liu Diao Yang Xue Wang Liu Diao Di