数据结构-几种O(n2)的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 选择排序，每次从准备排序的列表中，挑一个最小或(最大)的出来，慢慢的列表就空了。
def selectSort(l):
    for k ,v in enumerate(l):
        index= 0 # index用来记录 最小的数的下标
        smallNumber = float('inf')
        for i in range(k,len(l)):# 挑一个最小的数出来
            if l[i] < smallNumber:
                smallNumber = l[i]
                index= i
        # 更换，index和k下标上两者的值
        l[k],l[index] = smallNumber,l[k]
    return l

print(selectSort([54,26,93,17,77,31,44,55,20]))

1
2
3
4
5
6
7
8
9
10
11
12
# 冒泡排序 时间复杂度为 O(n2)
def  bubbleSort(l):
    for i in range(len(l)):
        for j in range(i+1,len(l)):
            if l[i]>l[j]:
                l[i],l[j] = l[j],l[i]
    return l




print(bubbleSort([3,4,5,2,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 insertionSort(alist):
    for k , v in enumerate(alist): # v 是要插入的值
        index = k # 记录当前的下标
        while index >0  and alist[index-1] >v: ##从下标1开始插入，也就是第二个
            alist[index] = alist[index-1]
            index -=1 # 从后往前插入比较,看是否更合适的插入点
        alist[index] = v # 插入


# 插入2的时候的比较
# 34521
# 34551
# 34451
# 33451
# 23451 alist[0] = 2

# 插入1 的时候的比较
# 23451
# 23455
# 23445
# 23345
# 22345
# 12345


print(insertionSort([3,4,5,2,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
# 希尔排序
def shellSort(l):
    subListCount  = len(l)//2 # 设定的增量
    while subListCount >0:
        # 分组
        for i in range(subListCount):
            # 组内部进行插入排序
            gapInsertionSort(l,i,subListCount)
        subListCount //=2
    return l
# 这就是一个插入排序,只是列表不在是连续的了，而是有了间隔
def gapInsertionSort(l,start,gap):
    # 循环组,这里间隔gap得到一个组
    for i in range(start,len(l),gap):
        index = i
        value = l[i]

        while  index+1 >gap and l[index-gap] >value:
            l[index] = l[index - gap]
            index -=gap
        l[index] = value


print(shellSort([5,3,2,1,4]))