本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。上篇已经介绍了前三种~给出原文链接如下：程序员面试必备之排序算法汇总(上)
四、归并排序
1.介绍
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2.步骤
（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
（4）重复步骤3直到某一指针达到序列尾
（5）将另一序列剩下的所有元素直接复制到合并序列尾
3.python实现
#encoding=utf-8 def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return result def merge_sort(lists): # 归并排序 if len(lists) <= 1: return lists num = len(lists) // 2 #python3 //区别/ left = merge_sort(lists[:num]) right = merge_sort(lists[num:]) return merge(left, right) array = [49, 38, 65, 97, 76, 13, 27, 49] list1 = merge_sort(array) print(list1)
4.视觉效果展示
五、堆排序
1.介绍
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
2.步骤（略）
3.python实现
#encoding=utf-8 #沿左,右子节点较大者依次往下调整 def heapify( array, i, n ): j = i * 2 + 1 while j < n: if j + 1 < n and array[j] < array[j + 1]: j += 1 if array[i] > array[j]: break array[i], array[j] = array[j], array[i] i = j j = i * 2 + 1 #创建堆 def build_heap( array ): size = len( array ) for i in range( size // 2 - 1, -1, -1 ): heapify( array, i, size ) #大顶堆排序 def heap_sort( array ): size = len( array ) build_heap( array ) #交换堆顶与最后一个结点,再调整堆 for i in range( size - 1, 0, -1 ): array[0], array[i] = array[i], array[0] heapify( array, 0, i ) a = [ -3, 1, 3, 0, 9, 7 ] heap_sort( a ) print( a )
4.视觉效果展示
六、选择排序
1.介绍
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
2.步骤（略）
3.python实现
#encoding=utf-8 def select_sort(lists): # 选择排序 count = len(lists) for i in range(0, count): min = i for j in range(i + 1, count): if lists[min] > lists[j]: min = j lists[min], lists[i] = lists[i], lists[min] return lists a = [ -3, 1, 3, 0, 9, 7 ] select_sort( a ) print( a )
4.视觉效果展示
七、冒泡排序
1.介绍
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
2.步骤
（1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
（3）针对所有的元素重复以上的步骤，除了最后一个。
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3.python实现
#encoding=utf-8 def bubble_sort(lists): # 冒泡排序 count = len(lists) for i in range(0, count): for j in range(i + 1, count): if lists[i] > lists[j]: lists[i], lists[j] = lists[j], lists[i] return lists a = [ -3, 1, 3, 0, 9, 7 ] bubble_sort( a ) print( a )
4.视觉效果展示
以上就是本期的内容，欢迎小伙伴们扫码订阅点赞噢~
