Nibaaa's diary note book


悟已往之不谏，知来者之可追

排序算法及其O(n)

  • ~3.12K 字
  1. 1. 简单记一下ADE里的排序算法及其big-Oh
    1. 1.1. 1.bubble sort: O(n^2)
    2. 1.2. 2.selection sort: O(n^2)
    3. 1.3. 3.insertion sort: O(n^2)
    4. 1.4. 4.merge sort: O(n*log(n))
    5. 1.5. 5.quick sort: O(n^2)

简单记一下ADE里的排序算法及其big-Oh

1.bubble sort: O(n^2)

1
2
3
4
5
6
7
8
9
10
def bubble_sort(ls):
   #  print(f"the origin list is {ls}")
    temp = 0
    for i in range(len(ls)-1,-1,-1):
        for j in range(i):
            if(ls[j]>ls[j+1]):
                temp = ls[j]
                ls[j] = ls[j+1]
                ls[j+1] = temp
   #  print(f"after bubble sort {ls}")

2.selection sort: O(n^2)

虽然还是O(n^2)，但是比冒泡少一点swapping

1
2
3
4
5
6
7
8
9
10
11
12
def selection_sort(ls):
   #  print(f"the origin list is {ls}")
    for i in range(len(ls)-1, -1, -1):
        pos_biggest = 0
        for j in range(i+1):
            if(ls[pos_biggest]<ls[j]):
                pos_biggest = j
        if(pos_biggest!=i):
            temp = ls[pos_biggest]
            ls[pos_biggest] = ls[i]
            ls[i] = temp
   #  print(f"after selection sort {ls}")

3.insertion sort: O(n^2)

1
2
3
4
5
6
7
8
9
10
def insertion_sort(ls):
   #  print(f"the origin list is {ls}")
    for i in range(1,len(ls)):
        temp = ls[i]
        j = i
        while(j>0 and ls[i-1]>temp):
            ls[j] = ls[j-1] #move the bigger one back one position
            j = j-1
        ls[j] = temp #place the temp at j(j might become smaller than i)
   #  print(f"after insertion sort {ls}")

4.merge sort: O(n*log(n))

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
31
def merge_sort(list):
    l = len(list)
    if(l==1 or l==0):
        return list
    m = l//2
    list1 = list[:m]
    list2 = list[m:l]
    list1 = merge_sort(list1)
    list2 = merge_sort(list2)
    ptr1=0
    ptr2=0
    i = 0
    while(i<l):
        if(list1[ptr1]>list2[ptr2]):
            list[i] = list2[ptr2]
            ptr2 = ptr2+1
        else:
            list[i] = list1[ptr1]
            ptr1 = ptr1+1
        i = i+1
        if(ptr1>=m and i<l):
            for j in range(i,l):
                list[j] = list2[ptr2]
                ptr2=ptr2+1
            break
        elif(ptr2>=l-m and i<l):
            for j in range(i,l):
                list[j] = list1[ptr1]
                ptr1=ptr1+1
            break
    return list

5.quick sort: O(n^2)

  • 在此的代码为in place类型，空间复杂度O(1)
  • worst case下pivot为min或max值，此时类似bubble sort
  • best case下pivot为midean值，此时类似merge sort
  • average case下pivot一般为1/3到2/3的值(拆分的list长度在1/3到2/3之间)，仍为O(n*log(n))
    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
    def quickSort(list, left, right):
        if(right-left < 1):
            return list
        # random_num = random.randint(left, right)
        random_num = left
        pivot = list[random_num]
        k, j = left, right
        new_pivot_idex = 0
        while(k<j): #repeat until j and k cross
            if(list[k]>=pivot):
                if(list[j]<pivot):
                    temp = list[k]
                    list[k] = list[j]
                    list[j] = temp
                    k=k+1
                    j=j-1
                else:
                    j = j-1
            else:
                k=k+1
        while(k+1<=len(list)-1 and list[k+1]<pivot):
            k=k+1
        new_pivot_idex = k
        quickSort(list, left, new_pivot_idex)
        quickSort(list, new_pivot_idex+1, right)
        return list
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可