前言
排序算法，可以说是编程中使用最多的算法之一了，而我们了解最多的排序算法，恐怕是冒泡排序了，这个算法比较好理解，稳定，不过时间也复杂度也是O(n^2)了效果也不是很好。也有很多效果比这个好的算法，或者排序比较巧妙的算法，例如：选择排序，插入排序，快速排序，归并排序，桶排序，堆排序等等。排序算法那么多，真的突然让我去介绍一个排序算法，我还不一等能够说的出来，下面就记录几个常用的排序算法。
对于Java，Python都会有已经写好的排序算法，例如Python中的sort和sorted方法，为什么我们还要去学习这些，其实在解决一些问题的时候对数组进行排序可以解决其他问题，这就是我们要学习其思想的原因。
注：以下排序都是默认升序的。
1 选择排序
选择排序，你可以这样理解，我们先把一个数组从前往后分为两部分，第一部分就是空，第二部分就是整个数组，我们可以依次从第二个部分中拿出最小的数插到第一部分中，依此类推直至把第二部分中的元素取完。其实，这个排序方式的算法复杂度也是O(n^2)，代码实现如下：
array = [7, 5, 3, 6, 44, 22, 99, 11]
def select_sort(alist):
n = len(alist) # 数组的长度
for i in range(n - 1): # 最后的那个值必然是最大的
# 剩余列表中最小值的索引
min_index = i
min_num = alist[i] # 默认第二部分中的第一个值最小
for j in range(i + 1, n):
if alist[min_index] > alist[j]:
min_index = j
# 交换
if min_index != i:
alist[i], alist[min_index] = alist[min_index], alist[i]
select_sort(array)
print(array)
2 插入排序
插入排序的核心思想就是将一个列表分为两个部分，一部分是排序的，一部分没有排序，我们逐次将没有排序的元素，在已排序序列中从后往前扫描找到对应位置并插入。换句话说，就是将无序的部分插入到有序的部分中。默认数组中第一个值就是有序的，然后就剩下的部分。最好的情况就是全部有序，那么算法的时间复杂度就是O(n)了，并且该算法是稳定的。
另外：这里可以使用二分查找的方式提速。
array = [7, 5, 3, 6, 44, 22, 99, 11]
def insert_sort(alist):
n = len(alist)
for j in range(1, n):
i = j
# 无序不中的元素插入到有序的序列中
while i > 0:
if alist[i] < alist[i-1]:
alist[i], alist[i-1] = alist[i-1], alist[i]
else:
break
i -= 1
insert_sort(array)
print(array)
3 快速排序
快速排序就是通过一趟排序将需要排序的数据分割为独立的两部分，首先任意选取一个数据（通常选用列表的第一个数）作为基准数据，然后将所有比它小的数都放在它左边，比它大的数放在右边，到只有两个元素的时候，就自动排好序了，递归回去时就就把上一层的数据排好序了，不过算法不稳定。
array = [7, 5, 3, 6, 44, 22, 99, 11]
def quick_sort(alist, start, end):
#递归退出条件
if start >= end: return
mid = alist[start] # 默认基准数位需要排序数组的第一个数
low, high = start, end
while low < high:
# 从右向左alist[high] > mid 则high -= 1
while low < high and alist[high] >= mid:
high -= 1
# 将high索引对应的元素赋值给low
alist[low] = alist[high]
# 从左往右list[low] < mid low +=1
while low < high and alist[low] < mid:
low += 1
alist[high] = alist[low]
# 将基准数防止到对应的位置
alist[low] = mid
# 比基准数小的即左边的数据 要重复调用quick_sort()
quick_sort(alist, start, low - 1)
# 比基准数大的即右边的数据 要重复调用quick_sort()
quick_sort(alist, low + 1, end)
quick_sort(array, 0, len(array) - 1)
print(array)
4 归并排序
归并排序也是使用递归的方法，需要辅助数组，辅助数组中存放是，当前需要合并的结果，合并的方式是：使用两个指针p1,p2，分别指向两个需要比较数组数组的开始的第一个值，然后比较这个指针指向的值，将较小的数放到辅助数组中，然后移动对应的指针进行下一次的比较，算法复杂度O(nlogn)，稳定的。
array = [7, 5, 3, 6, 44, 22, 99, 11]
def merge_sort(alist):
# 分解
n = len(alist)
# 递归出口
if n <= 1:return alist
mid = n//2
left_list = merge_sort(alist[0: mid])
right_list = merge_sort(alist[mid:])
# 合并，排序结果列表
result = []
left_pointer, right_pointer = 0, 0
while left_pointer < len(left_list) and right_pointer < len(right_list):
if left_list[left_pointer] <= right_list[right_pointer]:
result.append(left_list[left_pointer])
left_pointer += 1
else:
result.append(right_list[right_pointer])
right_pointer += 1
# 退出循环，将不为空的列表剩余元素添加到result中
# result += left_list[left_pointer:]
result.extend(left_list[left_pointer:]) # 效率更快
# result += right_list[right_pointer:]
result.extend(right_list[right_pointer:])
# 返回排序后的内容
return result
res = merge_sort(array)
print(res)
总结
排序算法较多，思想也比较独特，理解清楚这些算法后，对解决其他问题有很大的好处。
个人订阅号