排序与查找-冒泡和选择

[TOC]

冒泡排序Bubble Sort

  • 冒泡排序的算法思路在于对无序表进行多趟比较交换，
  • 每趟包括了多次两两相邻比较， 并将逆序的数据项互换位置， 最终能将本趟的最大项就位
  • 经过n-1趟比较交换， 实现整表排序❖每趟的过程类似于“气泡”在水中不断上浮到水面的经过
    • 第1趟比较交换， 共有n-1对相邻数据进行比较
      一旦经过最大项，则最大项会一路交换到达最后一项
    • 第2趟比较交换时， 最大项已经就位， 需要排序的数据减少为n-1， 共有n-2对相邻数据进行比较
    • 直到第n-1趟完成后， 最小项一定在列表首位， 就无需再处 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

def shortBubbleSort(alist):
    passnum = len(alist)-1
    while passnum > 0:
       for i in range(passnum):
           if alist[i]>alist[i+1]:
               exchanges = True
               temp = alist[i]
               alist[i] = alist[i+1]
               alist[i+1] = temp
            # python 支持直接交换值，alist[i],alist[i+1] = alist[i+1],alist[i]
       passnum = passnum-1

alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)

冒泡排序：算法分析

  • -无序表初始数据项的排列状况对冒泡排序没有影响

  • 算法过程总需要n-1趟， 随着趟数的增加， 比对次数逐步从n-1减少到1， 并包括可能发生的数据项交换。

  • 比对次数是1～ n-1的累加：

  • 比对的时间复杂度是O($n^2$)
  • 最好的情况是列表在排序前已经有序， 交换次数为0

  • 最差的情况是每次比对都要进行交换， 交换次数等于比对次数,平均情况则是最差情况的一半

  • 冒泡排序通常作为时间效率较差的排序算法， 来作为其它算法的对比基准。其效率主要差在每个数据项在找到其最终位置之前，必须要经过多次比对和交换， 其中大部分
    的操作是无效的。但有一点优势， 就是无需任何额外的存储
    空间开销。

冒泡排序：性能改进

  • 另外， 通过监测每趟比对是否发生过交换， 可以提前确定排序是否完成
  • 这也是其它多数排序算法无法做到的
  • 如果某趟比对没有发生任何交换， 说明列表已经排好序， 可以提前结束算法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

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  ##############
               temp = alist[i]
               alist[i] = alist[i+1]
               alist[i+1] = temp
       passnum = passnum-1

alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)


注意：在高度无序的情况下，可能没啥用，还可能减慢速度，多了判断和赋值

选择排序Selection Sort

  • 选择排序对冒泡排序进行了改进， 保留了其基本的多趟比对思路， 每趟都使当前最
    大项就位。

  • 但选择排序对交换进行了削减， 相比起冒泡排序进行多次交换， 每趟仅进行1次交
    换， 记录最大项的所在位置， 最后再跟本趟最后一项交换

  • 选择排序的时间复杂度比冒泡排序稍优比对次数不变，还是O($n^2$)交换次数则减少为O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

参考：

https://www.runoob.com/w3cnote/selection-sort.html