选择排序
搜索整个列表,找到最小项的位置。如果该位置不是列表的第一个位置,则交换这两个位置。然后算法回到第二个位置并且重复这个过程。如果必要的话,将最小项和第二个位置的项交换。当达到整个过程额最有一个位置。列表就是排序好的了。
import random
def selection_sort(lyst):
"""
:param lyst: 需要排序的列表
:return:
"""
def swap(lyst, i, j):
"""交换项目中 i 和 j的位置"""
# 可以理解为 lyst[i], lyst[j] = lyst[j], lyst[i]
temp = lyst[i]
lyst[i] = lyst[j]
lyst[j] = temp
i = 0
while i < len(lyst) - 1:
min_index = i
j = i + 1
while j < len(lyst):
if lyst[j] < lyst[min_index]:
min_index = j
j += 1
if min_index != i:
swap(lyst, min_index, i)
i += 1
else:
return lyst
if __name__ == '__main__':
size = 10
lyst = []
for count in range(size):
lyst.append(random.randint(1, size + 1))
print(lyst)
print(selection_sort(lyst))
package main
import "fmt"
func swap(lyst []int, i int, j int) {
temp := lyst[i]
lyst[i] = lyst[j]
lyst[j] = temp
}
func main() {
// 申明一个空slice
lyst := []int{100, 900, 111, 99, 56, 103, 78, 95, 1000, 789, 134, 110}
fmt.Println(lyst)
i := 0
for i < len(lyst) -1 {
min_index := i
j := i + 1
for j < len(lyst) {
if lyst[j] < lyst[min_index] {
min_index = j
}
j += 1
}
if min_index != i {
swap(lyst, min_index, i)
}
i += 1
}
fmt.Println(lyst)
}
在各种情况下复杂度为O($n^2$); 由于数据交互只在外围循环中进行,所以在最坏的情况下和平均情况下,开销是线性的。