软件设计师考试 - 排序算法

   一、排序的概念

   1. 稳定排序与不稳定排序

   稳定排序：相等元素排序后相对位置不变。

   不稳定排序：相等元素相对顺序可能颠倒。

   2. 内排序（内存排序）和外排序（外部存储排序）

   二、排序方法分类

   1.  插入类排序： 直接插入排序、希尔排序

   2. 交换类排序： 冒泡排序、快速排序

   3. 选择类排序： 简单选择排序、堆排序

   4. 归并排序

   5. 基数排序 

   三、常见的排序算法介绍

   1.  直接插入排序

   直接插入排序：即当插入第个记录时，R1，R2，...，Ri-1 均已排好序，因此，将第 i 个记录 Ri 依次与Ri-1，…，R2，R1进行比较，找到合适的位置插入。它简单明了，但速度很慢。

   排序思路：

   1. 首先将前面两个元素进行比较，按照从小到大的顺序

   2. 上面比较之后，得到一个有两个元素的有序数列。再将第三个元素与前面最大的元素相比，直到找到比它自己小的元素，插入到其后面...

   如下图：

   时间复杂度：O（n²）；空间复杂度：O（1）

   2. 希尔排序

希尔排序比直接插入排序要复杂一些，结合直接插入排序
希尔排序：先分组，经过前面几轮比较后，基本有序，再进行直接插入排序，彻底分配好
排序思路：当排序的数列比较小的时候，直接插入排序的效率还可以 （缩小解决问题的规模）

   时间复杂度和空间复杂度