前段时间在看计算机科学科学及编程导论，其中谈到了排序的各种算法，在这我浅谈四种插入，选择，冒泡，以及堆排序。
首先需要知道算法是什么？
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令程序的效率的一部分是由算法的时间复杂度或者是空间复杂度决定。这四种算法我用时间复杂度来分析
插入排序
插入排序一个经典的列子整理扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
伪代码
list sort_insert(list):
for i<-len(list) :
for j <-i:
if list[i]>list[j]:
Exchanging position
return list
代码块
def insert_sort(sort_list):
for i in range(len(sort_list)):
for j in range(i):
if sort_list[i] > sort_list[j]:
sort_list[j], sort_list[i] = sort_list[i], sort_list[j]
print sort_list
return sort_list
时间复杂度为o(n^2)
测试
sort_list = [8, 3, 4, 2, 6]
insert_sort(sort_list)
结果：
[8, 3, 4, 2, 6]
[8, 3, 4, 2, 6]
[8, 4, 3, 2, 6]
[8, 4, 3, 2, 6]
[8, 6, 4, 3, 2]
选择排序
选择排序是一种简单直观的排序算法。工作原理，首先在未排序序列中找到最小（大）元素，存放在排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素
伪代码
list select_sort(list):
for i <-range(len(list):
for j=i+1 <-range(len(list)):
if list[j]<list[i]
Exchange postion
代码
def select_sort(sort_list):
for i in range(len(sort_list)):
for j in range(i+1,len(sort_list)):
if sort_list[j] < sort_list[i]:
sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
print sort_list
return sort_list
时间复杂度为o(n^2)
测试
sort_list = [8, 3, 4, 56, 6, 1
select_sort(sort_list)
结果：
[1, 8, 4, 56, 6, 3]
[1, 3, 8, 56, 6, 4]
[1, 3, 4, 56, 8, 6]
[1, 3, 4, 6, 56, 8]
[1, 3, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]
3.冒泡排序
冒泡排序是临近的数字两两进行比较，按照从小到大或者从大到小的顺序进行交换
伪代码
list bubble_list(list):
for i<-len(list) :
for j <-range(1,len(list)-i):
if list[j-1]>list[j]:
Exchanging position
return list
代码
def bubble_sort(sort_list):
for i in range(len(sort_list)):
for j in range(1,len(sort_list) - i):
if sort_list[j] < sort_list[j-1]:
sort_list[j-1], sort_list[j] = sort_list[j], sort_list[j-1]
print sort_list
return sort_list
时间复杂度为o(n^2)
测试
sort_list = [8, 3, 4, 56, 6, 1]
bubble_sort(sort_list)
结果：
[3, 4, 8, 6, 1, 56]
[3, 4, 6, 1, 8, 56]
[3, 4, 1, 6, 8, 56]
[3, 1, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]
4.堆排序
堆排序利用了堆这种数据结构设计的一种排序算法，分了小堆和大堆，满足子节点总是小于父节点
# 创建最大堆
for start in range((len(list) - 2) // 2, -1, -1):
sift_down(list, start, len(list) - 1)
# 堆排序
for end in range(len(list) - 1, 0, -1):
list[0], list[end] = list[end], list[0]
sift_down(list, 0, end - 1)
return list
#最大堆调整
def sift_down(lst, start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and lst[child] < lst[child + 1]:
child += 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break
时间复杂度为n*log2n
百万级数据上堆排序是相对于其他三个排序更加适合，插入一般不用在数量超过一千的场合下，插入的最好时间复杂度为o(n) 最差为o(n^2) ，而冒泡和选择是对数级增长，一般并不推荐使用
