问题
填空题
对于长度为n的序列,在最坏情况下,简单选择排序需要______次比较。
答案
参考答案:n(n-1)/2
解析: 选择排序的基本思想是:扫描整个线性表,从中选出最小的元素,将它交换到表的最前面;然后对剩下的子表采用同样的方法,直到子表空为止。对于长度为n的序列,选择排序需要扫描n-1遍,每一遍扫描均从剩下的子表中选出最小的元素,然后将该最小的元素与子表中的第1个元素进行交换。在最坏情况下,简单选择排序需要,n(n-1)/2次比较。