常见排序算法

常见排序算法有很多种，这里仅列举冒泡排序、插入排序、选择排序、归并排序。

冒泡：现有一个列表有n项，每一轮比较的次数：当前未比较项数-1，且每一轮产生一个最大值，

时间复杂度：最好O（n），一般及最坏O（n方）

 1 # for实现
 2 lst = [7,9,3,11,45,23,12,87,234,12,5,93]
 3 n = len(lst)
 4 
 5 for i in range(n-1):
 6     flag = True
 7     for j in range(n-1-i):
 8         if lst[j] > lst[j+1]:
 9             lst[j],lst[j+1] = lst[j+1],lst[j]
10             flag = False
11     if flag :
12         break
13 
14 print('lst: ',lst)
15 
16 # while实现
17 lst1 = [7,9,3,11,45,23,12,87,234,12,5,93]
18 i = 1
19 n = len(lst1)
20 
21 while i < n:
22     j = 0
23     flag = True
24     while j < n-i:
25         if lst1[j] > lst1[j+1]:
26             lst1[j],lst1[j+1] = lst1[j+1],lst1[j]
27             flag = False
28         j += 1
29     if flag:
30         break
31     i += 1
32 
33 print('lst1:',lst1)

运行结果：

lst:  [3, 5, 7, 9, 11, 12, 12, 23, 45, 87, 93, 234]
lst1: [3, 5, 7, 9, 11, 12, 12, 23, 45, 87, 93, 234]

插入排序：每次取一个新数字与已取过数字比较，每轮后取过的数字都排好顺序，时间复杂度O（n方）

 1 lst = [3,88,76,23,999,22,888,56,39,72]
 2 
 3 for i in range(len(lst)):
 4     key = lst[i]
 5     j = i-1
 6     while j >= 0 and lst[j]> key:
 7         lst[j],lst[j+1] = lst[j+1],lst[j]
 8         j -= 1
 9 
10 print('lst: ',lst)

运行结果：

lst:  [3, 22, 23, 39, 56, 72, 76, 88, 888, 999]

选择排序：每一轮排出一个最小值，时间复杂度also is O（n方），但是因为交换次数少，速度比冒泡快

 1 lst = [7,9,3,11,45,23,12,87,234,11,5,93]
 2 n = len(lst)
 3 
 4 for i in range(n-1):
 5     small = i
 6     for j in range(i+1,n):
 7         if lst[j] < lst[small]:
 8             small = j
 9     if small != i:
10         lst[i],lst[small] = lst[small],lst[i]
11 
12 print('lst: ',lst)

运行结果：

lst:  [3, 5, 7, 9, 11, 11, 12, 23, 45, 87, 93, 234]

归并排序：原则是用递归先将序列分成最小两单元，然后排序再合并。。。最后将排好序的两个子序列再排序合并成一个有序序列

 1 def merge(a, b):
 2     c = []
 3     h = j = 0
 4     while j < len(a) and h < len(b):
 5         if a[j] < b[h]:
 6             c.append(a[j])
 7             j += 1
 8         else:
 9             c.append(b[h])
10             h += 1
11 
12     if j == len(a):
13         for i in b[h:]:
14             c.append(i)
15     else:
16         for i in a[j:]:
17             c.append(i)
18 
19     return c
20 
21 def merge_sort(lists):
22     if len(lists) <= 1:
23         return lists
24     mid = len(lists)//2
25     left = merge_sort(lists[:mid])
26     right = merge_sort(lists[mid:])
27     return merge(left, right)
28 
29 if __name__ == '__main__':
30     lst = [20,5,12,9,18,25,20,3]
31     print(merge_sort(lst))

运行结果：

[3, 5, 9, 12, 18, 20, 20, 25]

另一种写法：O（nlogn）

def merge(val):
    if len(val) > 1:　　　　
        mid = len(val)//2
        left = val[:mid]
        right = val[mid:]

        merge(left)
        merge(right)

        i = 0
        j = 0
        k = 0
        while i < len(left) and j < len(right):　　#left 和 right必有一边最终全部排完序，如left排完序后，最终情况是val是有序序列，left中也是有序序列
            if left[i] < right[j]:　　　　　　　　　　#接下来把left中未排序的元素全部加入val中即可
                val[k] = left[i]
                i += 1
            else:
                val[k] = right[j]
                j += 1
            k += 1
        while i < len(left):　　　　#此后两个while表示，谁在上一步没有排完序，就单独将其剩余元素加入val即可
            val[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            val[k] = right[j]
            j += 1
            k += 1
    return val

渐变 --> 突变