6, 7, 8]
总循环次数为 28
selection_sort 的结果 1 2 3 4 5 6 7 8
虽然得到了正确的结果,但是对于 [3, 4, 2, 1, 5, 6, 7, 8] 初始数据,...当然是可以的,在循环选取时,当最小元素的位置+1 = 最大元素的位置时,数据已经全部有序,可以退出。..., 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
总循环次数为 12
selection_sort2 的结果 1 2 3 4 5 6 7 8
从结果可以看出比未优化版的总循环次数少了...在实际应用中,当数据量很大时,优化的结果还是很可观的。
性能分析
首先,选择排序的只需要一个变量做为交换,因此空间复杂度是O(1),是一种原地排序算法。...选择排序无论数据初始是何种状态,均需要在未排序元素中选择最小或最大元素与未排序序列中的首尾元素交换,因此它的最好、最坏、平均时间复杂度均为 O(n^2)。