冒泡排序
从列表的开头处开始,并且比较一对数据项,直到移动到列表的末尾。每当成对的两项之间的顺序不正确的时候,算法就交换其位置。然后,算法从列表开头到倒数第二个列表项重复这一过程,依次类推,直到该算法从列表的最后一项开始执行。此时,列表是已经排序好的。
import random
def bubble_sort(lyst):
"""冒泡排序 最坏的复杂度是O(n**2), 最好的情况下冒泡排序不会进行任何交换
: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
n = len(lyst)
while n > 1:
i = 1
while i < n:
if lyst[i] < lyst[i - 1]:
swap(lyst, i, i-1)
i += 1
n -= 1
else:
print(f"排序后内存地址为:{id(lyst)}")
return lyst
if __name__ == '__main__':
size = 10
lyst = []
for count in range(size):
lyst.append(random.randint(1, size + 1))
print(lyst)
print(f"排序前内存地址为:{id(lyst)} \n")
print(bubble_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() {
lyst := []int{100, 900, 111, 99, 56, 103, 78, 95, 1000, 789, 134, 110}
fmt.Println(lyst)
n := len(lyst)
for n > 1 {
i := 1
for i < n {
if lyst[i] < lyst[i -1] {
swap(lyst, i, i-1)
}
i += 1
}
n -= 1
}
fmt.Println(lyst)
}
在最坏的情况下,一共需要 $\frac{1}{2} n^2-\frac{1}{2}n$ 次。因此,冒泡排序最坏的情况复杂度是$ O(n^2)$。