冒泡和简单选择排序算法

python3
算法

冒泡排序(Bubble Sort又称为泡沫排序或气泡排序):
是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端,而最大数在第一次的外循环就固定了
实例分析

以列表[5, 1, 4, 2, 8] 为例说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 第一次外循环
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), 5 > 1 交换位置
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 交换位置
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 交换位置
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 5 < 8 位置不变
# 第二次外循环(除开最后一个元素8,对剩余的序列)
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 1 < 4 位置不变
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 交换位置
( 1 2 4 5 8 ) → ( 1 2 4 5 8 ), 4 < 5 位置不变
# 第三次外循环(除开已经排序好的最后两个元素,
# 可以注意到上面的数组其实已经排序完成,但是程序本身并不知道
# 所以还要进行后续的循环,直到剩余的序列为 1)
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
# 第四次外循环(最后一次)
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    n =  0
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
                n+=1
    print(n)
    return lists
print(bubble_sort([5,1,4,2,8]))
print(bubble_sort([8,5,4,2,1]))
# 输出如下
# 4
# [1, 2, 4, 5, 8]
# 10
# [1, 2, 4, 5, 8]

简单选择排序算法:
在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止.

以列表[5, 1, 4, 2, 8] 为例说明
第一趟: 1,5,4,3,8
第二趟: 1,3,4,5,8
第三趟: 1,3,4,5,8
第四趟: 1,3,4,5,8
第五趟: 1,3,4,5,8

代码实现:

1
2
3
4
5
6
7
8
9
10
`def select_sort(lists):
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists
print(select_sort([5, 1, 4, 2, 8]))

Share Comments