软考：排序_软考 排序最好最坏复杂度

    该文章是关于数据结构部分排序的总结，包括各种排序方法的时间和空间复杂度的分析，主要从直接插入、交换（冒泡、快速）、选择（直接选择、堆排序）和归并四类来分析。

直接插入：

    依次将每个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。具体：插入第i个记录时，前i-1已经排好序，此时将第i个记录的关键字和第i-1，i-2比较，从而找到插入位置插入位置及其后记录依次向后移动。

    举例：9  6 15 8 11

         复杂度： 直接插入最好情况下每趟只需做一次比较且不用移动元素，因此n个元素总比较次数n-1，总移动0次；最坏情况下进行第j趟排序时与前面每个记录都有比较，双重循环，此时是关于n^2的式子；又排序过程中仅需一个元素的辅助空间，空间复杂度O（1），且是稳定排序。

交换：

        冒泡：首先将第一个记录键值和第二个记录键值比较，如果R[1].key>R[2].key，则交换，然后继续比较第二个和第三个，比较n-1次后完成最大记录在