一、内部排序

1. 排序sorting是计算机程序设计中的一种重要操作，它的功能是将一个数据元素或记录的任意序列，冲洗排列称一个
   按关键字有序的序列。有序表可以进行二分查找，构造树（二叉排序或B-树）的过程本身是一个排序的过程
2. 稳定的排序方法，两个或多个关键字相等,序号i<j,排序后i<j
   不稳定的排序方法，会出现i>j
3. 内部排序：排序的记录数量很少，待排序记录存放在计算机随机存储器内存中进行排序的过程
   外部排序：排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
4. 依据不通的原则对内部排序方法进行分类，大致可分为:
    a. 插入排序
    b. 交换排序
    c. 选择排序
    d. 归并排序
    e. 计数排序
5. 依据内部排序过程中所需工作量来区分：
    a. 简单对排序方法 O(n2)
    b. 先进对排序方法 O(nlogn)
    c. 基数排序O(d*n)
6. 排序对过程中序进行下列两种基本操作：
    a. 比较两个关键字对大小,必要的
    b. 将记录从一个位置移动到另一个位置，根据选择的存储方式，可选
7. 待排序的记录序列又如下三种存储方式:
    a. 顺序存储,数组，要移动
    b. 一组待排序记录存放在静态链表中，修改指针，链表排序
    c. 待排序记录存放在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，
       在排序过程中不移动记录本身，而移动地址向量中这些记录的地址，在排序结束后再按照地址向量
       中的值调整记录的存储位置。地址排序

二、插入排序

1. 直接插入排序，基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
   n个记录，走n-1趟，每次比较移动, 时间复杂度O(n2)
2. 折半插入排序：减少查找操作O(n2)
3. 2-路插入排序: 中间，比较，之前或之后O(n2)
4. 表插入排序: 静态链表，0表头结点，表头结点取关键字最大整数，首先标记地址，其次重新排列
5. 希尔排序：缩小增量排序，基本思想：先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，
           待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
           2个一组，全部。增量序列可以有各种取法，但需要注意，应使增量序列中的值美誉除1之外的公因子，
           并且最后一个增量值必须是1。 增量序列:..,9,5,3,2,1 或40,13,4,1

三、快速排序

0. 借助“交换”进行排序的方法，不稳定
1. 冒泡排序(bubble sort):n-1次循环，交换，每次找出最大的 O(n2)
2. 快速排序：是对冒泡排序对改进，基本思想是，通过一趟排序将待排记录分割成独立对两部分，其中一部分记录的
           关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
   关键字，low指针，high指针，递归，1分为2，数量级O(nlogn)
   通常快速排序被认为是，在所有同数量级的排序方法中，其平均性能最好。
   枢纽选取：r[s].key,r[t].key r[(r+t)/2].key取三者中关键字取中值的记录为枢纽。
   若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为冒泡排序O(n2)
   需要栈空间,如果没有交换记录的操作，则可以不在进行排序

四、选择排序,不稳定

1. 基本思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。
2. 简单选择排序：每次 从n-i+1个记录中通过n-i次关机字间的比较，选出关键字最小的记录，并和第i个记录交换，O(n2)
3. 树形选择排序：又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录关键字进行两两比较，
              然后在其中n/2个较小者之间在进行两两比较，如此重复，直至选出最小关键字的记录为止。
              完全二叉树表示。O(nlogn),需要较多的辅助存储空间
4. 堆排序(Heap Sort)只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
   可以用数组表示，完全二叉树，每次都构造一个小顶堆或大顶堆。
   两个问题：如何由一个无序序列建成一个堆，如何调整剩余元素成为一个新的堆
   从n/2个元素开始进行筛选，序列最后一个元素调整，heapSort函数和headAdjust函数
   堆排序方法堆记录数量较小的文件并不值得提倡，对n记录数量较大对文件还是很有效的。
   堆排序在最坏的情况下，其时间复杂度也为O(nlogn)，此外堆排序仅需一个记录大小供交换用的辅助存储空间。

五、归并排序(MergingSort)，稳定

1. 基本思想，将两个或两个以上的有序表组合成一个新的有序表。总体时间复杂度O(nlogn)
   无论是顺序存储结构还是链表存储结构，一趟时间复杂度都是O(m+n)
2. 2路归并排序：核心操作是将一维数组中前后相邻的两个有序序列归并成为一个有序序列.
3. 递归实现和非递归实现，递归的实现性很差,MSort,MergeSort

六、基数排序

1. 基数排序是一种借助多关键字进行排序的思想，
2. 基数排序是借助分配和收集两种操作堆单逻辑关键字进行排序的一种内部排序方法。
3. 多关键字，扑克花色和大小，主排序，次排序
4. 链式基数排序，静态链表，时间复杂度O(d(n+rd))

七、总结

    排序方法    平均时间       最差情况        辅助空间
    简单排序    o(n2)         o(n2)          o(1)
    快速排序    o(nlogn)      o(n2)          o(logn)
    堆排序      o(nlogn)      o(nlogn)       o(1)
    归并排序    o(nlogn)      o(nlogn)       o(n)
    基数排序    o(d(n+rd))    o(d(n+rd))     o(rd)
1. 从平均时间性能而言，快速排序最佳，最快情况下不如（堆排序和归并排序)
2. 堆排序和归并排序，在n较大的时候，归并排序所需时间较省，但需要较多的存储空间
3. 简单排序包括除希尔排序的所有插入排序，冒泡排序，简单选择排序，都比较简单，n较小时或基本有序，可用
4. 基数排序的时间复杂度O(d*n),它适用于n值较大而关键字较小的序列。