最近在慕课网上学习了O（n2）时间复杂度的相关算法，总算是对这些算法的优缺点有了详细的特点。其实对于任何的算法，没有优点和缺点，而是有相应的特点。所以我们应该结合不同的排序环境来选择不同的排序算法，从而达到在实现时间和执行效率上的平衡。这是因为，越是简单的排序算法，实现起来肯定是越容易，而且出现BUG的概率也不会太大。相反，复杂算法可能效率更高，但是出现问题的可能性也会更大。下面，我就结合O（n2）时间复杂度的四个经典排序算法，为您详细讲解这四个算法的特点。
选择排序
定义：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
图示说明：
源码实现：
template
void selectionSort(Tarr[],int n)
{
for(int i = 0; i < n; i++)
{
int minIndex = i;
for(int j = i; j < n; j++)
{
if(arr[minIndex] >= arr[j])
{
minIndex = j;
}
}
if(minIndex != i)
{
swap(&arr[minIndex], &arr[i]);
}
}
}
分析：通过选择排序的图示和源码我们可以看出来，选择排序要进行两次循环，而且最关键的是内层循环在每一次执行时都是全部执行完的。那我们有没有办法让内层循环不用每次都执行完呢？方法肯定是有的，这就是冒泡排序。
冒泡排序
定义：冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
图示说明：
源码实现：
template
void bubbleSort(Tarr[],intn){
for(int i = 0; i < n; i++)
{
intflag= 0;
for(intj = 0; j < n-i-1; j++)
{
if(arr[j] > arr[j + 1])
{
swap(arr[j], arr[j+1]);
flag= 1;
}
}
if(!flag)
{
break;
}
}
return;
}
分析：从图示和源码可以看出来，从执行次数上来说，冒泡排序是比选择排序的循环次数更少的。那是不是就可以说，如果待排序的数组中元素比较合适，冒泡排序在时间复杂度上是不是会比选择排序更好呢？真的是这样的吗？
其实不是的，经过多次测试验证，冒泡排序基本上是比选择排序的时间复杂度要差的，这是为什么呢？从源码中我们可以很明显的看出来，虽然冒泡排序是比选择排序执行次数少了，但是交换的次数明显增多了，而如果你对计算机程序指令的实现原理只要有一个基本的认识，就应该知道交换动作比赋值动作是需要更多指令操作的。所以说，最终冒泡排序大部分情况下，比选择排序的时间复杂度都要高。
既然交换动作这么消耗资源，那有没有一种方法，即能够减少内层循环的执行次数，又可以减少甚至是无需交换操作呢？这就要请出插入排序了。
插入排序
定义：插入排序（Insertion Sort）的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
图示说明：
源码实现：
template
void insertionSortX(Tarr[],int n)
{
for(int i = 1; i < n; i++)
{
Te =arr[i];
int j;
for(j = i; j > 0 && (arr[j - 1] > e); j--)
{
arr[j] =arr[j -1];
}
arr[j] = e;
}
}
分析：从图示和源码可以看出来，插入排序（优化后的）是没有交换操作的，而且对于内层循环来说，如果待排序的元素是比较大的值，那内层循环执行的次数会非常的少。因此，如果原始数据基本上是有序的，那使用插入排序的效率会非常的高。在O（n2）级别的排序算法还可以再优化吗？如果可以从哪里优化呢？下面我们来介绍希尔排序，正是这个排序算法的提出，使得排序算法打破了O（n2）时间复杂度的禁锢。
希尔排序
定义：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该算法的基本思想是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序算法便终止。
对于希尔排序来说，最关键的就是增量该如何选取。这个增量该怎么确定，这还真是个数学难题，至今没有解答。但是通过大量的实验，还是有个经验值的。我们的例子给出的增量选取公式是：h = 3 * h + 1，下面请看图示说明。
图示说明：
源码实现：
template
void shellSort(Tarr[],int n){
int h = 1;
while(h < n / 3)
{
h = 3 * h + 1;
}
while(h >= 1){
for(int i = h; i < n; i++)
{
Te = arr[i];
int j;
for(j = i; j >= h && (e <= arr[j - h]); j -= h){
arr[j] = arr[j -h];
}
arr[j] = e;
}
h = h / 3;
}
return;
}
分析：从插入排序中我们知道，插入排在待排序数组基本有序时，插入排序的算法效率会非常高，所以我们可以这样认为，希尔排序的最终思想就是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
而希尔排序的效率之所以很高，就是因为这个基本思想确实很有用：即当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。而当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。
对于增量的选取，可以称得上是一种魔法。在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
总结：上面就是四种经典O（n2）级别排序算法的相关说明。其实在各种场合下选择排序和冒泡排序基本上是不会使用的，因为使用场景基本没有。而对于插入排序和希尔排序来说，在待排序数据基本有序的情况下，使用场景还是有的，比如一些日志文件中存储的日志，可能大部分的日志记录都是基于时间排序，只是在某些极端情况下导致一些日志晚存储了导致时间不一致。
我是徐建航，这是我写的第31篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。
