这有一份八味排序餐

1、插入排序

1. 1 直接插入

原理

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。具体方法是第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

示例

待排序数组：

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 {,1,2,3,4,5,6,7,8,9}

Python3代码

1.2 希尔

原理

将待排序列划分(根据增量或者步长)为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排。增量的选取会影响算法的时间复杂度。

示例

待排序数组：

第一次步长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}

合并起来就是：

第二次步长h=1，那么数组按照步长只有1个数组了

对这个数组进行一次插入排序后，最终顺序就成为：

Python3代码

2、选择排序

2. 1 直接选择

原理

从待排序序列中，找到关键字最小的元素；如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。

示例

待排序数组：

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代码

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，则整个排序过程完成；

示例

待排序数组，升序

1，生成最大堆

2，互换——生成最大堆 重复

排序结果

Python3代码

3、交换排序

3. 1 冒泡

原理

临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样遍历过一次数组后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束排序。

示例

待排序数组，升序

第一次遍历(外循环)

第1次两两比较8 > 6，需要交换(内循环)：交换前状态交换后状态

第2次两两比较8

第3次两两比较9 > 3，需要交换(内循环)：交换前状态交换后状态

结束比较

第二次遍历(外循环)

第1次两两比较6

第2次两两比较8 > 3，需要交换(内循环)：交换前状态交换后状态

结束比较

第三次遍历(外循环)

第1次两两比较6 > 3，需要交换(内循环)：交换前状态交换后状态

结束比较

第四次遍历(外循环)

无交换，结束内循环

结束外循环遍历，排序结束

Python3代码

3. 2 快速

原理

先从数列中取出一个数作为基准数，分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，再对左右区间重复第二步，直到各区间只有一个数。

示例

待排序数组：

第1次：

基准数=6，首先，用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走；

i 往右走，直到遇见不小于基准数的值停止移动 5。j 向左走，直到遇见不大于基准数的值停止移动 2，交换两个值的位置 ；

i，j继续移动，i停在1，j和i相遇，停止移动，1和基准数互换位置，；

第2次：

待排序数组：基准数1； 基准数7。重复上面操作

Python3代码

4、归并排序

4. 1 归并

原理

该算法采用经典的分治(divide-and-conquer)策略，将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。

示例

待排序数组：

分

治

Python3代码

5、分配排序

5. 1 基数

原理

基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：分配，先从个位开始，根据个位值(0-9)分别放到0至9号桶中（比如53,个位为3，则放入3号桶中)；收集，再将放置在0至9号桶中的数据按顺序放到数组中。从最低位到最高位重复分配与收集过程。

示例

待排序数组：

Python3代码