1

You are given a list of 100 integers that have been read from a file. If all values are zero, what would be the running time (in terms of O-notation) of a selection sort algorithm.

I thought it was O(n) because selection sort starts with the leftmost number as the sorted side. then it goes through the rest of the array to find the smallest number and swaps it with the the first number in the sorted side. But since they are all zeros then it won't swap any numbers (or so I think).

my teacher said that it is O(n^2). can anyone explain why?

4

1 回答 1

1

选择排序不是自适应的。每个元素将始终与其他元素进行比较（将 n 个元素与 n 个其他元素进行比较 → n^2 次比较）。因此，选择排序总是有 O(n^2) 比较。然而，它有 O(n) 的交换。

想象一个有 n 行 n 列的表格，每个单元格都需要一个比较来填充值（对角线除外）。

这个惊人的网站上的更多信息

于 2013-05-19T09:52:27.493 回答