对有n个记录的表r[1…n]进行直接选择排序,所需要进行的关键字间的比较次数为______。

admin2010-12-16  38

问题 对有n个记录的表r[1…n]进行直接选择排序,所需要进行的关键字间的比较次数为______。

选项

答案n(n-1)/2

解析 选择排序的思想为:扫描整个线性表,从中选出最小的元素,将它交换到表的最前面;然后对剩下的子表采用同样的方法,直到子表空为止。第一个元素需要比较n-1次,第二次元素需要比较n-2次,依次类推,倒数第二个元素只须比较1次即可,所以总的比较次数为:(n-1)+(n-2)+…2+1=n(n-1)/2。
转载请注明原文地址:https://kaotiyun.com/show/PBVp777K
0

最新回复(0)