排序算法之七大排序算法的区别与应用场合
直接插入排序
shell排序（希尔）
选择排序
堆排序
冒泡排序
快速排序
归并排序
一、属于交换排序的有以下两种：
①快速排序
基本思想:选取一个基准元素，通常为数组最后一个元素（或者第一个元素）。从前向后遍历数组，当遇到小于基准元素的元素时，把它和左边第一个大于基准元素的元素进行交换。在利用分治策略从已经分好的两组中分别进行以上步骤，直到排序完成。下图表示了这个过程。
时间复杂度与空间：
稳定性差，产生跳跃交换。数据敏感性高，对于本来就有序的数据，排序效率最低，需要采取优化方式。
适用场景：
1.一般应用中，比其他排序快得多，适用于数组长度比较大的情况，对于小数组，快速排序比插入排序慢。
2.如果数组中有大量重复元素，则用优化版快排比标准的快排效率高很多。
备注：
具体优化版的快排如何实现，请参考我下一篇博文。
②冒泡排序
基本思想：比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面。
时间复杂度与空间：
稳定性差，产生跳跃性的交换。并且数据敏感，对于数据量少，数据有序度高的数组，时间较快。
适用场景：
1.适用元素较少的情况下，元素太多的话，交换和比较次数都会很多，影响效率，元素多的情况适合用快速排序。
2.当数组基本有序的情况下适合使用冒泡排序和直接插入排序，它们在基本有序的情况下排序的时间复杂度接近O(n)。
二、属于插入排序的有以下两种：
1.直接插入排序
基本思想：和交换排序不同的是它不用进行交换操作，而是用一个临时变量存储当前值。当前面的元素比后面大时，先把后面的元素存入临时变量，前面元素的值放到后面元素位置，再到最后把其值插入到合适的数组位置。
时间复杂度与空间：
适用场景：
适用于数据量小于100的基本有序数据，这样的数据，直接插入排序会很快，超过了快速排序的速度。
2.希尔排序
基本思想为在直接插入排序的思想下设置一个最小增量dk,刚开始dk设置为n/2。进行插入排序，随后再让dk=dk/2,再进行插入排序，直到dk为1时完成最后一次插入排序，此时数组完成排序。
时间复杂度与空间：
适用场景：
希尔排序是对直接插入排序的一种优化，可以用于大型的数组，希尔排序比插入排序和选择排序要快的多，并且数组越大，优势越大。
三、属于选择排序的有以下两种：
1.直接选择排序
基本思想：依次选出数组最小的数放到数组的前面。首先从数组的第二个元素开始往后遍历，找出最小的数放到第一个位置。再从剩下数组中找出最小的数放到第二个位置。以此类推，直到数组有序。
时间复杂度与空间：
适用场景：
数据量不大，并且对稳定性没有要求的情况。
2.堆排序
基本思想：先把数组构造成一个大顶堆（父亲节点大于其子节点），然后把堆顶（数组最大值，数组第一个元素）和数组最后一个元素交换，这样就把最大值放到了数组最后边。把数组长度n-1,再进行构造堆，把剩余的第二大值放到堆顶，输出堆顶(放到剩余未排序数组最后面)。依次类推，直至数组排序完成。
时间复杂度与空间：
适用的场景：
1.堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
2.优先队列通常用堆排序来实现。
3.堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
四、归并排序：
基本思想：归并算法应用到分治策略，简单说就是把一个答问题分解成易于解决的小问题后一个个解决，最后在把小问题的一步步合并成总问题的解。这里的排序应用递归来把数组分解成一个个小数组，直到小数组的数位有序，在把有序的小数组两两合并而成有序的大数组。
时间复杂度与空间：
适用场景：
1.适用于数据量特别庞大时，内部储存器不足以一次性处理这么多数据，则可适用分治的思想，将数据量分割成若干份，分别排序并归并，一般来说，归并排序与插入排序配合适用。
2.若要求排序稳定，则可选用归并排序。但前面介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子序列，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。