1、直接插入排序
def insert_sort(seq_list):
if not seq_list:
return None
seq_list_len = len(seq_list)
if seq_list_len < 2:
return seq_list
# 认为第一个是有序
for i in range(1, seq_list_len):
key = seq_list[i] # 带排序的数
j = i - 1
while j >= 0 and seq_list[j] > key:
seq_list[j+1] = seq_list[j]
j -= 1
seq_list[j+1] = key
return seq_list
if __name__ == '__main__':
import random
my_list = range(10)
random.shuffle(my_list)
# [1, 4, 8, 9, 7, 2, 5, 6, 0, 3]
print insert_sort(my_list)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2、冒泡排序
def bubble_sort(seq_list):
i = len(seq_list)
print i
while i > 1:
max = seq_list[0] # 每次选第一个作为最大值
for j in range(i):
if seq_list[j] < max: # 如果遇到比最大值小的，交换位置，大的往上冒
seq_list[j], seq_list[j-1] = seq_list[j-1], seq_list[j]
max = seq_list[j]
if seq_list[j] > max:
max = seq_list[j]
i -= 1
return seq_list
if __name__ == '__main__':
import random
my_list = range(100)
random.shuffle(my_list)
print bubble_sort(my_list)
3、选择排序
def select_sort(seq_list):
seq_list_len = len(seq_list)
i = 0
while i < seq_list_len:
item = min(seq_list[i:]) # 用了min来求一个列表的最小值
j = seq_list[i:].index(item) + i # 使用index求下标,应该求剩下未排序列表中元素的下标，绝对下标要加上i
seq_list[i], seq_list[j] = item, seq_list[i] # 最小值放在未排序数组的第一个位置，第一个位置数放在存放最小值的位置
i += 1
return seq_list
if __name__ == '__main__':
import random
my_list = range(100)
random.shuffle(my_list)
print select_sort(my_list)
4、快排
def quick_sort(seq_list):
if not seq_list:
return seq_list
else:
pivot = seq_list[0] # 将列表的第一个元素定位轴
small = quick_sort([x for x in seq_list[1:] if x < pivot]) # 比轴小的放一边，比轴大的放一边，然后递归对左子表进行快速排序，右子表进行快速排序
big = quick_sort([x for x in seq_list[1:] if x >= pivot]) # 这里因为第一个作为轴，所以从下标1开始筛选
return small + [pivot] + big
if __name__ == '__main__':
print quick_sort([1,2,3,10,2,3,4])
