数据结构学习-python实现-数据排序--0411

# 冒泡法排序。每次从所有的数据项中，将最大的数据移动到最后。
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]


testlist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubblesort(testlist)
print(testlist)
# 冒泡排序是排序的基础，方法简单，但是每个过程都不会省略，可以用于判断复杂度的基石。
# 比对的时间复杂度是O(n²)
# 交换的时间复杂度是O(n²)
# 未占用额外空间

# 优化冒泡排序算法，假设中途就排好了顺序，就不用执行剩下的步骤，在此算法中增加了判断是否有数据的顺序交换。
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 -= 1  # 缩小规模，否则死循环


alist = [20, 31, 41, 91, 51, 61, 71, 81, 101, 111]
shortbubblesort(alist)
print(alist)
# 若数据均匀分布，此算法并不会比简单冒泡算法快，甚至出现更复杂。原因是数据均匀，无天然形成的顺序数据，反而
# 增加了判断交换的步骤，导致变得复杂。

# 选择排序，与冒泡排序的方法相同，每趟记录最大项的下标位置，与最后一个值交换。并不需要每步都交换。
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

        alist[fillslot], alist[positionofmax] = alist[positionofmax], alist[fillslot]
# 比对的时间复杂度是O(n²)
# 交换的时间复杂度是O(n)，减少了一个数量级
# 未占用额外空间

# 插入排序，新思路，从第二个值开始，判断位置，将其插入序列当中
def insertionsort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]  # 保存当前值为临时变量，因为它的位置由于插空，将被占用。
        position = index  # 当前比较值的位置
        while position>0 and alist[position-1]>currentvalue:
            alist[position] = alist[position-1]  # 较大值后移的过程
            position = position -1  # 空位前移的过程

        alist[position] = currentvalue  # 将当前值放入空位

# 谢尔排序，有点复杂，以插入排序做依托，将列表分成两半，运用递归的思想
def shellsort(alist):
    sublistcount = len(alist) // 2  # 划分数据
    while sublistcount > 0:  # 递归停止条件
        for startposition in range(sublistcount):  # 在各间隔进行数据大小比对，将较小值放在靠前
            gapinsertionsort(alist, startposition, sublistcount)  # 交换过程
        print('after increment of size', sublistcount, 'the list is', alist)
        sublistcount = sublistcount // 2  # 规模缩小
          
def gapinsertionsort(alist, start, gap):
    for i in range(start+gap, len(alist), gap):  # 将位置至于靠后的数据之上
        currentvalue = alist[i]  # 将当前值存于临时变量之中
        position = i  # 保存当前位置

        while position >= gap and alist[position-gap] > currentvalue:
            alist[position] = alist[position-gap]  # 在当前位置放置较大值
            position = position - gap  # 换到靠前位置

        alist[position] = currentvalue  # 靠前位置放置较小值


blist = [9, 8, 7, 6, 5]

shellsort(blist)
print(blist)

# 复杂度为O(n1.5)