Py008-01-05选择排序和插入排序

选择排序(体育老师一指禅法)

思路：

在一个列表里每次把最小的值取出来。

简易版本(不建议用)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
li = [3,2,4,6,5,1,8,7,9]

def select_sort1(li):
    list_new = []
    for i in range(len(li)):
        min_val = min(li)
        list_new.append(min_val)
        li.remove(min_val)

    return list_new

res = select_sort1(li)
print(res)

'''
我们知道  冒泡排序是交换彼此直接的位置，属于原地排序

而这个版本的选择排序  
每次都对原始数据进行删除  假如是长度10000的集合  如果满足条件的值在中间5000的位置  那么后边的要依次  索引-1
'''

优化版

1
2
3
4
5
6
7
8
9
10
11
def select_sort2(li):
    for i in range(len(li)-1): # i是第几趟
        min_loc = i
        for j in range(i+1,len(li)):
            if li[j]<li[min_loc]:
                min_loc = j
        li[i],li[min_loc] = li[min_loc],li[i]
        print(li)

res2 = select_sort2(li)
print(res2)
  • 一趟排序记录最小的数，放到第一个
  • 再一趟排序记录 列表无序区最小的数，放到第二个位置
  • 。。。。
  • 关键点：有序区 和 无序区，无序区最小值的位置

时间复杂度：O(n*n)

插入排序(起扑克牌法)

你玩过扑克吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
你是如何摸牌的？
比如 arr = [5,1,3,2,4]

()内为你摸到的牌

第一次摸到5 
(5) [1,3,2,4]
第二次摸到1   1与5比=>小 交换位置
(1,5) [3,2,4]
第三次摸到3   3与5比=>小 交换位置   3与1比=>大 不交换
(1,3,5) [2,4]
第四次摸到2   2与5比=>小 交换位置   2与3比=>小 交换位置   2与1比=>大 不交换
(1,2,3,5) [4]
第五次摸到4  4与5比=>小 交换位置   4与3比=>大  不交换

插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def insert_sort(li):
    for i in range(1,len(li)): # 表示摸到的牌的下标
        tmp = li[i]
        j = i-1 # 手里牌的下标
        while j>=0 and li[j]>tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
        print(li)

li = [3,2,4,6,5,1,8,7,9]

insert_sort(li)

时间复杂度： O(n*n)