排序一览表

一：简单插入排序（1）基本思想

简单来说：简单插入排序将整个序列分为有序和无序两组，开始时默认第一个数字就是有序序列，接着挑选无序序列中的第一个数字，与有序序列数字（从后向前）挨个比较，如果小于继续比较前一个，直到某一时刻大于有序序列中的某个数字时，将将其插入在后面，然后扫描下一个无序序列中的数字。

（2）代码

排序数组为：int a[] = { 9,1,2,5,7,4 };

单趟排序

为了便于讲述具体排序过程，下面给出一趟排序的具体流程，代码如下

根据以上代码可以给出如下流程

完整排序

经过以上分析，要进行完整排序，只需从第二个元素开始，挨个向前插入到有序序列当中去。

所以简单插入排序可以总结为：把一个序列分成有序和无序两个部分，有序序列位于[0,end]，无序序列[end,n-1]，不断把[end,n-1]中的元素插入[0,end]区间内。

（3）动态演示（4）分析

简单插入排序在序列基本有序时，效率很高，时间复杂度也很低，但是当一个序列高度无序时，就会显得很吃力，尤其是像基本无序的序列，使用简单插入排序就很伤。

所以简单插入排序适用于数据元素较少，且基本有序的情况。当然它的一些后序会用希尔排序将其优化

（5）视频演示

点击我的头像查看合集

二：希尔排序（1）基本思想

希尔排序又叫做增小缩量排序。是对简单插入排序的一种优化，其基本思想是：选定一个整数gap，以gap为组距，将原序列分成若干组，对每个组进行简单插入排序，完成之后，gap再缩小，重复以上步骤。带待到gap=1时，整个序列已经基本有序了，其最后一次进行的排序就是简单插入排序，但是这一次的排序相比直接用简单插入排序，其时间复杂度大大降低了。

（2）代码

1：单趟排序，分组论述

还是假设gap=3，对这几组进行排序的过程如下

代码如下（展示蓝色那一组的排序）

可以发现经过这一趟排序后，序列又接近有序了。

所以gap越大，越大的数据越容易跑到后面，越小的数据越容易跑到前面。gap越大，越不接近有序，gap越小，越接近有序。当gap=1时就是简单插入排序

2：单趟排序

上述代码有一个问题就是，它只能完成蓝色那一组排序，对于绿色和紫色则不行，因为由有gap的控制。所以说按照正常的相反，就是有多少组就搞出多少组for循环进行控制。但是如果这样做，希尔排序可能就没有存在的意义了。所以希尔排序它的巧妙之处就在于：多趟并排。

代码如下

具体过程如下

3：完整排序

最后一步，理应就是控制趟数。前面说过gap过大过小都不好。研究表明gap控制在3左右效果最好。为了使最后一次gap=1，使gap=gap/3+1，这样无论gap设为多少，总是在最后一次能进行增量1的简单插入排序。

（3）动态演示

图片转载自：十大经典排序算法（动图演示）

（4）分析

希尔排序是对插入排序的优化，如果一个序列完全逆序，那么这种优化十分明显，比如生成一个十万个元素的数据，完全逆序，采用直接插入排序所用的时间为

而采用希尔排序，这一时间竟然会压缩到

（5）视频演示

点击我的头像查看合集

三：直接选择排序（1）基本思想

和简单插入排序有所区别。直接选择排序默认认为整个序列是无序的，每次从这个无序序列中选出一个最小（或最大）的元素放到这个无序序列的首位。放在首位的元素，就被划分为了有序序列，然后无序序列的个数自然少一个了，然后重复上述过程

（2）代码

1：单趟排序

单趟排序的过程如下

2：完整排序

所以从上面可以看出，每趟排序结束后，无序序列就缩小了，等价于上图中的begin不断增大，所以完整代码如下

（3）动态演示（4）分析

直接选择分析很好理解，但是效率低，所以一般不会使用

（5）视频演示

太简单了，略

四：堆排序

关于堆和堆排序相关内容，请移步

数据结构系列_6：堆与堆排序

（5）视频演示

点击我的头像查看合集

五：冒泡排序（1）基本思想

冒泡排序属于交换类排序，简单点来说**，每趟排序不断比较相邻元素的大小然后进行交换**，这样如果按升序排序，那么最大的元素一定就会交换到最后面，次大的元素会交换到倒数第二位，依次类推。

（2）代码

1：完整排序

可以发现，当完成一趟排序之后，无序序列的元素就少了一位，那么需要排序的元素的位数也就少了一位。

所以定义一个变量end，它表示每趟排序指向此时无序序列的最后一个元素，然后对其进行排序，一趟结束之后，无序元素少一位，end向前移动，直到end=0时，表示排序结束。

关于这个代码当中要注意那个flag的设置，因为如果某趟排序排完之后，使得整个序列已经有序了，那么就没有必要再次排序了，所以设立flag就是要确保还进入了排序，说明此时还不是完全有序。

（3）动态演示（5）视频演示

太简单了，略

六：快速排序

快速排序内容较多，请移步

数据结构系列8-快速排序1(基本实现与弊端处理)

数据结构系列8_快速排序2：优化及非递归实现

（3）动态演示（5）视频演示

快速排序1：基本实现与弊端处理

七：归并排序

归并排序内容较多，请移步

数据结构系列_9：归并排序

（3）动态演示（5）视频演示

点击我的头像查看合集

横向总结