欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

冒泡和选择排序算法

程序员文章站 2024-03-19 22:15:04
...

冒泡排序

时间复杂度O(n2)O(n^2)

  • 冒泡排序的算法思路在于对无序表进行多趟比较交换
  • 每趟包括了多次亮亮相邻比较,并将逆序的数据项互换位置,最终能将本趟的最大项就位
  • 经过n-1趟比较交换,实现整表排序
  • 每趟的过程类似于“气泡”在水中不断上浮到水面的过程

具体过程:

  • 第1趟比较交换,共有n-1对相邻数据进行比较(一旦经过最大项,则最大项会一路交换到达最后一项);
  • 第2趟比较交换时,最大项已经就位,需要排序的数据减少为n-1,共有n-2对相邻数据进行比较;
  • 直到第n-1趟完成后,最小项一定在列表首位,就无需再处理了。
def bubbleSort(alist):
    for passnnum in range(len(alist) - 1, 0, -1):
        for i in range(passnnum):
            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)

选择排序

  • 选择排序对冒泡排序进行了改进,保留了其基本的多趟比对思路,每趟都使当前最大项就位。
  • 但选择排序对交换进行了削减,相比起冒泡排序进行多次交换,每趟仅进行1次交换,记录最大项的所在位置,最后再跟本趟最后一项交换
  • 选择排序的时间复杂度O(n2)O(n^2),比起冒泡稍优
    对比次数不变还是O(n2)O(n^2),交换次数减少为O(n)O(n)
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)
相关标签: 算法随笔