参考答案

参考回答：

1、插入排序，即逐个处理待排序的记录，每个记录与前面已排序的子序列进行比较，将它插入子序列中正确位置，时间复杂度O（n^2）,空间复杂度为O(1)，是稳定排序，插入排序不适合对于数据量比较大的排序应用，但是如果量级小余千，那么插入排序还是一个不错的选择，

2、冒泡排序，它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。他的时间复杂度和空间复杂度分别是O（n^2）,空间复杂度是O（1）属于稳定排序，冒泡排序对于少数元素之外的数列排序是很没效率的。

3、选择排序，初始时在序列中找到最值元素，放到序列的其实位置作为已排序序列，再在剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。他的时间复杂度是O（n^2）,空间复杂度是O（1）属于不稳定排序

4、shell排序，是插入排序的升级版，属于不稳定排序，希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或直接插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。希尔排序的时间复杂度根据步长序列的不同而不同，空间复杂度O（1）

5、归并排序，归并排序的实现分为递归实现与非递归(迭代)实现。属于稳定排序，递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。他的时间复杂度是O（nlogn）空间复杂度是O（n）

6、堆排序，其实现原理为首先将数组构造成一个最大/最小堆，将堆顶元素和堆尾元素互换，调出堆顶元素，重新构造堆，重复步骤直至堆中元素都被调出。堆排序的时间复杂度为O（nlogn）空间复杂度为O（1），属于不稳定排序。

7、快速排序，快排使用分治策略，首先从序列中挑出一个元素作为基准，然后把比基准小的元素放在一边，把比基准大的元素放在另一边，重复这个步骤，直至子序列的大小是0/1.快排的时间复杂度是O（nlogn）空间复杂度是O（logn）属于不稳定算法，对于快排的基准元素选取，可以采用三者取中法，三个随机值的中间一个。为了减少随机数生成器产生的延迟，可以选取首中尾三个元素作为随机值

排序算法的适用情况：

当n比较小且基本有序，可采用直接插入或冒泡，否则采用直接插入

当n较大，可以采用快排，归并，堆排序，快排是目前基于比较的内部排序中最好的方法，堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
若要求排序稳定，则可选用归并排序。但前面介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子序列，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。