有沒有任何情況下，選擇排序不會排序列表直到第n遍？

Question

在我的編程書中，它有選擇排序運行n每次傳遞一個n大小的列表。有沒有需要第n次通過的情況？第n-1代每次都不會將第n-1個元素與第n個元素交換？

Answer 1

它需要n-1次通過。 （n-1）+（n-2）+ ...... +（n-k）+ ... 3 + 2 + 1 = n（n-1）/ 2，其複雜度爲O（n^2）