pythonfan.png
1、插入排序
1.1 直接插入
原理
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。具体方法是第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。示例
待排序数组：{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}
i=1： 5 {5, 6, 3, 1, 8, 7, 2, 4, 9, 0}
i=2： 3 {3, 5, 6, 1, 8, 7, 2, 4, 9, 0}
i=3： 1 {1, 3, 5, 6, 8, 7, 2, 4, 9, 0}
i=4： 8 {1, 3, 5, 6, 8, 7, 2, 4, 9, 0}
i=5： 7 {1, 3, 5, 6, 7, 8, 2, 4, 9, 0}
i=6： 2 {1, 2, 3, 5, 6, 7, 8, 4, 9, 0}
i=7： 4 {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
i=8： 9 {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
i=9： 0 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Python3代码
# 直接插入排序 def Insert(listdata): for i in range(1, len(listdata)): # 设置当前值前一个元素的标识 j = i - 1 # 如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位 if listdata[i] < listdata[j]: temp, listdata[i] = listdata[i], listdata[j] # 继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素 j = j - 1 while j >= 0 and listdata[j] > temp: listdata[j + 1] = listdata[j] j = j - 1 # 将临时变量赋值给合适位置 listdata[j + 1] = temp return listdata
1.2 希尔
原理
将待排序列划分(根据增量或者步长)为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排。增量的选取会影响算法的时间复杂度。示例
待排序数组：{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}
第一次步长h=4，那么数组按照步长可以拆分成4个小数组（[0]6的意思是下标[0]的值为6）
{[0]6, [4]8, [8]9}
{[1]5, [5]7, [9]0}
{[2]3, [6]2}
{[3]1, [7]4}
对这4个小数组分别进行插入排序后，4个小数组变成：
{[0]6, [4]8, [8]9}
{[1]0, [5]5, [9]7}
{[2]2, [6]3}
{[3]1, [7]4}
合并起来就是：{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}
第二次步长h=1，那么数组按照步长只有1个数组了{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}
对这个数组进行一次插入排序后，最终顺序就成为：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Python3代码
# 希尔排序def Shell(listdata): n = len(listdata) # 希尔增量 gap = int(n / 2) while gap > 0: # 按增量进行直接插入排序 for i in range(gap, n): j = i # 直接插入排序 while j >= gap and listdata[j - gap] > listdata[j]: listdata[j - gap], listdata[j] = listdata[j], listdata[j - gap] j -= gap # 得到新的增量 gap = int(gap / 2) return listdata
image
2、选择排序
2.1直接选择
原理
从待排序序列中，找到关键字最小的元素；如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。示例
待排序数组：{6, 5, 3, 1, 8, 7}
i=1： {1, 5, 3, 6, 8, 7} 最小值1，交换6和1
i=2： {1, 3, 5, 6, 8, 7} 最小值3，交换5和3
i=3： {1, 3, 5, 6, 8, 7} 最小值5，无需交换
i=4： {1, 3, 5, 6, 8, 7} 最小值6，无需交换
i=5： {1, 3, 5, 6, 7, 8} 最小值7，交换7和8
i=6： {1, 3, 5, 6, 7, 8} 最小值8，无需交换，结束排序Python3代码
# 直接选择排序def Select(listdata): for i in range(len(listdata) - 1): minnum = i for j in range(i + 1, len(listdata)): if listdata[j] < listdata[minnum]: minnum = j listdata[i], listdata[minnum] = listdata[minnum], listdata[i] return listdata
2.2 堆
原理
堆分为最大堆和最小堆，其实就是完全二叉树。最大堆：父节点的值都不小于子节点的值，最小堆：父节点的值都不大于子节点的值。每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆(升序)或者最小堆(降序)，依次类推，最终得到排序的序列。
1， 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2， 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)；
3， 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成；示例
待排序数组{7, 13, 2, 9, 15}，升序
1，生成最大堆image
2，互换——生成最大堆 重复
image
排序结果{2, 7, 9, 13, 15}
Python3代码
# 堆排序 def adjust_heap(lists, i, size): lchild = 2 * i + 1 rchild = 2 * i + 2 max = i if i < size / 2: if lchild < size and lists[lchild] > lists[max]: max = lchild if rchild < size and lists[rchild] > lists[max]: max = rchild if max != i: lists[max], lists[i] = lists[i], lists[max] adjust_heap(lists, max, size) # 创建堆 def build_heap(lists, size): for i in range(0, (int(size/2)))[::-1]: adjust_heap(lists, i, size) # 堆排序 def Heap(lists): size = len(lists) build_heap(lists, size) for i in range(0, size)[::-1]: lists[0], lists[i] = lists[i], lists[0] adjust_heap(lists, 0, i) return lists
image
3、交换排序
3.1 冒泡
原理
临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样遍历过一次数组后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束排序。示例
待排序数组{8，6，9，3}，升序
第一次遍历(外循环)
第1次两两比较8 > 6，需要交换(内循环)：交换前状态{8，6，9，3}交换后状态{6，8，9，3}
第2次两两比较8 < 9，不需要交换(内循环)：状态{6，8，9，3}
第3次两两比较9 > 3，需要交换(内循环)：交换前状态{6，8，9，3}交换后状态{6，8，3，9}
结束比较
第二次遍历(外循环)
第1次两两比较6 < 8，不需要交换(内循环)：状态{6，8，3，9}
第2次两两比较8 > 3，需要交换(内循环)：交换前状态{6，8，3，9}交换后状态{6，3，8，9}
结束比较
第三次遍历(外循环)
第1次两两比较6 > 3，需要交换(内循环)：交换前状态{6，3，8，9}交换后状态{3，6，8，9}
结束比较
第四次遍历(外循环)
无交换，结束内循环
结束外循环遍历，排序结束
Python3代码
# 冒泡排序def Bubble(listdata): for i in range(len(listdata) - 1): # 这个循环负责设置冒泡排序进行的次数 for j in range(len(listdata) - i - 1): # ｊ为列表下标 if listdata[j] > listdata[j + 1]: listdata[j], listdata[j + 1] = listdata[j + 1], listdata[j] return listdata
3. 2 快速
原理
先从数列中取出一个数作为基准数，分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，再对左右区间重复第二步，直到各区间只有一个数。示例
待排序数组：{4, 5, 3, 1, 7, 6, 2}
第1次：
基准数=6，首先，用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走；
i 往右走，直到遇见不小于基准数的值停止移动 5。 j 向左走，直到遇见不大于基准数的值停止移动 2，交换两个值的位置 {4, 2, 3, 1, 7, 6, 5}；
i，j继续移动，i停在1，j和i相遇，停止移动，1和基准数互换位置，{1, 2, 3, 4, 7, 6, 5}；
第2次：
待排序数组： {1, 2, 3} 基准数1；{7, 6, 5} 基准数7。重复上面操作
Python3代码
# 快速排序def Quick(listdata): if len(listdata) == 0: return [] pivots = [x for x in listdata if x == listdata[0]] lesser = Quick([x for x in listdata if x < listdata[0]]) greater = Quick([x for x in listdata if x > listdata[0]]) return lesser + pivots + greater
image
4、归并排序
4. 1 归并
原理
该算法采用经典的分治(divide-and-conquer)策略，将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。示例
待排序数组：{4, 5, 3, 1, 7, 6, 2, 9}
分
image
治
image
Python3代码
# 归并排序 def Merge(listdata): n = len(listdata) if n == 1: return listdata mid = n // 2 # 对分割的左半部分进行归并排序 leftdata = Merge(listdata[:mid]) # 对分割的右半部分进行归并排序 rightdata = Merge(listdata[mid:]) # 对排序之后的两部分进行合并 # 定义两个游标 left, right = 0, 0 merge_result_li = [] left_n = len(leftdata) right_n = len(rightdata) while left < left_n and right < right_n: if leftdata[left] <= rightdata[right]: merge_result_li.append(leftdata[left]) left += 1 else: merge_result_li.append(rightdata[right]) right += 1 merge_result_li += leftdata[left:] merge_result_li += rightdata[right:] # 将合并后的结果返回 return merge_result_li
image
5、分配排序
5. 1 基数
原理
基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：分配，先从个位开始，根据个位值(0-9)分别放到0至9号桶中（比如53,个位为3，则放入3号桶中)；收集，再将放置在0至9号桶中的数据按顺序放到数组中。从最低位到最高位重复分配与收集过程。示例
待排序数组：{4561, 349, 78, 12, 201, 9, 3208}image
Python3代码
# 基数排序def Radix(listdata): k = len(str(max(listdata))) # k获取最大位数 for k in range(k): # 遍历位数，从低到高 s = [[] for i in range(10)] # 生成存放数的十个桶 for i in listdata: # 遍历元素 s[i // (10 ** k) % 10].append(i) # 分配 listdata = [a for b in s for a in b] # 收集 return listdata
image
不同算法之间的对比：
pythonfan.png
image
作者：AiFan
链接：https://www.jianshu.com/p/ecc261b5d7cf