Java 实现的各种经典的排序算法小Demo

由于有上机作业，所以就对数据结构中常用的各种排序算法都写了个Demo，有如下几个：

直接插入排序

折半插入排序

希尔排序

冒泡排序

快速排序

选择排序

桶排序

<a href="http://download.csdn.net/detail/marksinoberg/9377526">Demo下载地址</a>

下面谈一谈我对这几个排序算法的理解：

对于直接插入排序：（按从小到大的顺序）

核心原理：

若数组中只有一个元素，那么这就已经是有序的了；若数组中元素个数为两个，我们只需要对他们进行比较一次，要么交换顺序，要么不交换顺序就可以实现数组的内容的有序化；但是当数组内的元素的个数为N个呢？又该如何？这就催化了这个直接插入排序算法，其核心就是利用了有序化数组的方式，认为再插入一个新的元素之前都是有序的，只需要从后往前进行查找（找到一个小于待插入数据的位置，记为position，然后把这个数据之后的元素全部向后迁移一个，再把待插入数据插入到position+1的位置即可。（小伙伴们可以想象一下为什么是position+1，因为position位置上的数据小于我们的待插入的数据啊，所以要插在Position的下一个位置上！）

关于折半插入排序算法：

折半插入的核心原理仍然是基于有序表的插入算法，找到位置后，仍然采用插入的方式进行数据添加。但是较之于直接插入有很大的提升，那就是在查找插入位置上的优化，速度上稍微有了一定的提升，虽然在乱序的数据上有良好的效果，但是时间复杂度仍然很大O(n^2)。是稳定的算法。

下面是代码的实现：

对于希尔排序：

希尔排序核心仍然是基于插入方式的，以逐步减小“步长”，采用“分治”的思想对每一个子序列进行排序。最终实现对整个序列的排序。

特点：希尔排序是不稳定的排序算法，会导致数据原始相对位置的改变。如果以步长为2计算，其时间复杂度可达到O(n^2)，若数据足够长，步长也足够大那么时间复杂度将接近与O(n),但是一般认为其为O(n^1.3)。

代码实现：

对于冒泡排序：

冒泡排序是我们接触比较早的一个排序算法，其原理就是对数据两两进行比较大小，并对符合要求的数据进行交换。循环n-1次，便可以对n 个数据实现排序。

特点：

时间复杂度O(n^2)，由于数据发生交换时并没有发生原始位置的变化，所以冒泡排序算法是稳定的排序算法。

对于冒泡排序，这里还有一个改进版的冒泡，是针对于特殊情况下的排序的处理，比如一个已经有序的序列如果再进行正常的冒泡的话，就会浪费时间，所以，如果一个序列已经是有序的，那么就应该跳出这个序列的冒泡，从而在一定程度上减少了时间的浪费。

快速排序算法：

快速排序的原理是找到轴值pivot（这里有两种方式，从代码中可以清晰地看到，但最终结果都是一样的，那就是找到这个分割点，再递归的进行排序。

特征：

时间复杂度为O(nlogn,已2为底)；

代码如下：

对于选择排序：

两轮循环，第一轮是选择的次数的记录，第二轮是目标查找。所谓目标查找，就是找到一个符合要求的值，记录其位置，然后在第一轮的循环中进行判断，将符合条件者进行交换，如此可实现排序的功能。

时间复杂度O(n^2),交换n-1次，比较了n^2次。是不稳定的排序算法。

代码：

对于归并排序：

若一个序列只有一个元素，则它是有序的，归并排序不执行任何操作。否则归并排序将执行下面的递归步骤：

1）先把序列划分为长度基本相等的子序列

2）对每个子序列归并并排序

3）把排好序的子序列合并为最终的结果。

时间复杂度O(nlogn)，是不依赖于数据原始顺序的不稳定的排序算法。

总结：

排序算法多种多样，在不同的情况下选择合适的排序算法能让你事半功倍。