冒泡排序
-
算法思想:
冒泡排序（Bubble Sort),是一种计算机科学领域的较简单的排序算法.它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端.
这是一个最简单基础的排序方法,通常它的时间效率比较差(O(n^2)),但是它不需要额外的存储空间. -
实现
python版本 3.7.2
def bubbleSort(alist):
for passnum in range(len(alist)-1, 0, -1):
for i in range(passnum):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubbleSort(alist)
print(alist)
改进版,在已经有序的情况下减少了比较次数.
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist) - 1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i] > alist[i+1]:
exchanges = True
alist[i], alist[i+1] = alist[i+1], alist[i]
passnum = passnum - 1
alist = [23, 56, 45, 12, 45, 87, 5, 3, 65, 65, 9, 22, 45, 41, 21, 21, 12]
shortBubbleSort(alist)
print(alist)
如有错误还望指出
|