“排序算法的比较”

一、算法的简介

1.插入排序
插入排序是一个对少量元素进行排序的有效算法，工作原理与很多人打牌时，整理手中牌时的做法差不多。在开始摸牌时，我们的左手是空的，牌面朝下放在桌上，接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的每一张牌从右到左地进行比较使得无论什么时候左手中的牌都是拍好序的。
2.合并排序
插入排序使用的是增量方法，而合并排序采用的是分治法。
合并排序直观的操作如下：
分解：将n个元素分成各含n/2个元素的子序列
解决：用合并排序法对两个子序列递归地排序
合并：合并两个已排序的子序列得到排序结果
在对子序列排序时，其长度为1时递归结束。单个元素被视为是已拍好序的。
3.冒泡排序
冒泡排序时一种流行的排序算法，重复地交换相邻的两个反序元素，就像冒泡泡一样。
4.快速排序
像合并排序一样，快速排序也是基于分治思想。
对数组A[p..r]快速排序的分治过程如下：
分解：数组A[p,r]被划分为两个（可能空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A[q]，而且，小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行计算
解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序
合并：因为两个子数组是就地排序的，将它们的合并不需要操作：整个数组A[p..r]已排序

二、算法的编程实现与测试（Java）

插入排序的代码实现如下：

合并排序的代码实现如下：

冒泡排序的代码实现如下：

快速排序的代码实现如下：

三、算法的性能分析

可以通过调节代码中的测试数组的个数N，来观察每个排序过程所用的时间，不一定说时间复杂度高的排序时间就更长，不同的排序算法对于不同的N，情况可能……结论需要大家动手实际操作一下啦！
对于时间复杂度：
快速排序的最好情况下与平均时间复杂度为O(nlgn)/最坏情况下的时间复杂度为O(n^2)
合并排序的所有情况下的时间复杂度为O(nlgn)
插入排序/冒泡排序的平均时间复杂度与最坏情况下的时间复杂度为O(n^2)，最好情况下的时间复杂度为O(n)