数据结构之树与图算法.ppt

思想: 每一趟都选出一个最大或最小的元素，并放在合适当的位置。 简单选择排序 树形选择排序 堆排序 选择排序 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 思想: 第 1 趟选择: 从 1—n 个记录中选择关键字最小的记录，并和第 1 个记录交换。 第 2 趟选择: 从 2—n 个记录中选择关键字最小的记录，并和第 2 个记录交换。 第n-1趟选择: 从 n-1—n 个记录中选择关键字最小的记录，并和第 n-1 个记录交换。 . . . 简单选择排序 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例，序列 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 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 直接选择排序的算法 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] ); } } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 选择排序的主要操作是进行关键字间的比较。 在 n 个关键字中选出最小值，至少需要 n-1 次比较。 在剩余的 n-1 个关键字中选出最小值，至少需要 n-2 次比较？ 如果能利用前 n-1 次比较所得信息，可以减少后面选择的比较次数。 体育比赛中的锦标赛: Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例，8 名运动员要决出 冠、亚、季军。 按简单选择排序需要比赛 7+6+5 = 18 场。 若能够利用以前的比赛结果，比赛场次实际可以减少为 11 场。 前提: 若 甲 胜 乙 ，乙 胜 丙 ，则 甲 必能胜 丙 。 Zhao Cha Liu Bao Diao Yang Xue Wang Bao Bao Diao Cha Bao Diao Wang 冠军 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 如何求 亚军？ Zhao Cha Liu Diao Yang Xue Wang Cha Diao Cha 亚军 可以利用前面的比赛结果！ Cha Liu Diao Wang Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose