最近很多同学问我关于排序算法的问题，像冒泡排序，选择排序。学过数据结构的还好说，对于没有接触过数据结构的同学来说内心基本是属于崩溃的。下面我就来总结一下数据结构中的八大排序算法。

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

排序（按关键字大小顺序排列数据）。
排序方法：内部排序，外部排序；简单的排序方法O(n2)，先进的排序方法O(nlogn)，基数排序O(dn)；插入排序，交换排序，选择排序，归并排序，计数排序。
排序方法的稳定性：取决于该方法采取的策略，不是由一次具体的排序结果决定的。但是通过列举不稳定的排序实例可以说明该排序算法的不稳定性。
1、直接插入排序
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
将待排序记录插入已排好的记录中，不断扩大有序序列。一句话，“将待排序记录插入有序序列，重复n-1次” 。

例：排序前: 6 3 3 5 6 3 1 0 6 4
i = 0: 6
i = 1: 3 6
i = 2: 3 3 6
i = 3: 3 3 5 6
i = 4: 3 3 5 6 6
i = 5: 3 3 3 5 6 6
i = 6: 1 3 3 3 5 6 6
i = 7: 0 1 3 3 3 5 6 6
i = 8: 0 1 3 3 3 5 6 6 6
i = 9: 0 1 3 3 3 4 5 6 6 6
排序后: 0 1 3 3 3 4 5 6 6 6

插入排序演示地址

算法实现

2、希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。
步骤：
1. 分成子序列(按照增量dk)；
2. 对子序列排序(直接插入排序)；
3. 缩小增量，重复以上步骤，直到增量dk=1。
增量序列中最后一个增量一定是1，如：… 9, 5, 3, 2, 1和… 13, 4, 1。如没有明确说明增量序列可以选择… 3, 2, 1或… 5, 3, 2, 1。

算法说明

3、选择排序
设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。
第i趟排序过程是在剩余的待排记录中选一个最小（大）的，放在第i个位置。
一句话，“在待排记录中选取最小的，交换到合适位置，重复n-1次” 。

算法实现

算法实现

对冒泡排序常见的改进方法是加入一标志性变量，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。可以参考折半查找法

改进后的算法实现为: