[数据结构与算法]排序算法；

一、基本概念

? ? ? ? 定义：将一系列的记录通过 关键字有序的序列。

? ? ? ? 稳定性：主关键字一样的记录，若排序前后顺序不变，则称其是稳定的，反之不稳定。

? ? ? ? 内排序和外排序：记录置于内存中为内排序，记录在内外存中不断交换是外排序。

二、冒泡排序(bubble sort)

? ? ? ?定义： 相邻两数据依次比较交换进行。O(n^2/)

? ? ? ? 优化：增加标记flag，如果在某一部步循环完没有产生数据交换，说明排序完成，不再进行后续的排序了。

三、简单选择排序

? ? ? ? 找到每次遍历过程中最小的哪个值放到最前面去。O(n^2)但是交换次数少了，性能更好

四、 直接插入排序。

? ? ? ? 利用一个记录的辅助空间，依次进行插入排序。使用于基本有序的记录集。1/4*n^，O(n^2)。

五、希尔排序

? ? ? ? 通过某个增量，将相隔增量的记录进行比较并交换（用辅助空间array[0])，增量以某种规律（公式推荐的决定的）逐渐减小至1即可。O(n^3/2)

六、堆排序

? ? ? ? 利用大顶堆进行排序，每次将最大的放置在层序遍历末尾后，将剩余的构建大顶堆，循环进行得到。O(nlogn)

? ? ? ? 堆：完全二叉树；每个结点值都大于等于其左右孩子结点的值为大顶堆；小于等于为小顶堆。

七、归并排序

? ? ? ? 将每个记录是为一个有序的子序列，然后将其两两归并并排序；再两两归并排序，如此反复，直到得到一个长度为n的有序序列为止，称为2路归并排序。O(nlogn)

八、快速排序