2018.01.02 周二--【技术文章】《常见排序算法》

1.概述

    常见的排序算法，虽然很基础，但是很见功力，如果能思路清晰，很快写出来各个算法的代码实现，还是需要花一点功夫的，今天，就跟大家盘点下常用的一些算法。

冒泡排序

插入排序

选择排序

希尔排序

堆排序

归并排序

快速排序

2.各个排序代码实现(PHP版本)

代码详见GitHub： http://t.cn/RHjBCU7

    2.1 冒泡排序

    1）【定义】：就是第一个位置上的数与他相邻第二个位置上的数比较，如果比他相邻的数小，则两者交换位置，否则不交换。接着第一个位置上的数与第三个位置上的数比较大小，也是小则交换，一直到和最后一个位置的数比较交换完毕。然后，是下一个循环，就是第二个位置上的数重复上面的比较交换操作，直到把整个数列变成是一个从小到大的有序序列。

    2）【代码实现】：两层for循环搞定。

冒泡排序

2.2 插入排序

    1）【定义】：从一堆待排序的数列中选出来一个最小值(可以认为第一个数就是已排序的数列)，然后从剩余的带排序的数列中选出来最小值有序放到已排序的数列中，依次操作，直到最后的数列都是一个从小到大的有序数列为止。

    2）【代码实现】：

插入排序

2.3 选择排序

    1）【定义】： 从一堆待排序的数列中选出来一个最小值，放到新的数组的第一个位置，继续从剩余的数列中选取最小值放入到数组中，重复上面的步骤，将数字都取出来排成新的有序数列。 

    2）【代码实现】：

选择排序主函数

选择排序子函数

2.4 希尔排序

    1）【定义】： 插入排序的一种改进，先比较一定距离的元素成为有序数列，再比较缩小增量距离的元素(可为元素的数量的一半)，一直到比较的是相邻元素的时候，就成为了插入排序。所以希尔排序是插入排序的改进。

    2）【代码实现】：

希尔排序

2.5 堆排序

1）【定义】：1️⃣构造大顶堆 2️⃣交换堆顶和堆底 3️⃣重复前面的步骤升序排列完成

    详细说明参看： https://www.cnblogs.com/chengxiao/p/6129630.html

2）【代码实现】

堆排序主函数heapSort()

堆排序子函数

2.6 归并排序

    1）【定义】：就是将待排序的数列看成是单个的有序的数列，然后进行合并，直到合并成最后的完成整有序的数列。

    详细可参考：https://www.cnblogs.com/jingmoxukong/p/4308823.html

    2）代码实现：

    主函数mergeSort(),两个子函数mergePass() 和 merge()

归并排序主函数mergeSort()

归并排序子函数mergePass()

归并排序子函数merge()

2.7 快速排序

1）定义：该算法的基本思想是：

    1．先从数列中取出一个数作为基准数。

    2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

    3．再对左右区间重复第二步，直到各区间只有一个数

2）代码实现：

快速排序

3.排序总结

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

排序算法比较