根据排序过程中设计的存储器不同，可将排序方法分为两大类
内部排序:待排序记录存放在计算机随机存储器中进行的排序过程
外部排序:指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外村进行访问的排序过程
//////////////////////////////////////////内部排序///////////////////////////////////////////////
内部排序的三种工作量(1)O(n*n) (2)O(n*logn)(3)O(d*n)
插入排序：
(1)直接插入排序：
将一个操作插入到以排好序的有序表中，从而得到一个新的，记录数增1的有序表
时间复杂度O(n*n)
(2)折半插入排序
在一个有序表中进行查找和插入，与直接插入的区别是这个用的是二分法查找
时间复杂度O(n*n)
(3)二路排序
创建相同大小的数组b，以原数组a的a[1]为标准，有两个指针，一个first指向最后，一个final指向开头，比b[1]小的去后面，比b[1]大的去前面
移动记录次数约为n*n/8，所以他的时间复杂度也为O(n*n)
(4)希尔排序（缩小增量排序）
已知直接排序，如果排序记录序列为"正序"那么时间复杂度可以提高至O(n)，由此可想，若待排记录序列按关键字"基本有序"，则直接插入的效率会大大增加
基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整改序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。
如十个数据，按照5，3，1的顺序，先一一排序，最后再一次直接插入
当n在某个范围内的时候时间复杂度O(n的1.3次方)
交换排序：
最为人熟知的是起泡排序，就不多说了，时间复杂度O(n*n)
(1)快速排序
基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。
具体做法：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pibotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。
就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法，被认为是所有同数量级(O(nlogn))的排序方法中，其平均性能最好。
O(nlogn)(但是如果记录序列按关键字有序或基本有序时，其时间复杂度退化为O(n^2)
选择排序：
普通：
基本思路：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1=<i<=n)个记录交换之。
时间复杂度O(n*n)
树形选择排序：
首先对n个记录的关键字进行两两排序，然后再其中[n/2]个较小者之间再进行两两比较，如此重复直至选出最小关键字的记录为止。
堆排序：
对于属性排序的改进，只需要一个记录大小的辅助空间
堆排序在最坏的情况下时间复杂度也为O(n*logn)，这是它优越于快速排序的最大特点
归并排序：
将两个或是以上的有序表结合成一个新的有序表，它的实现方法早已为读者所熟悉，无论是顺序存储结构还是链表存储结构，都可在O(m+n)的时间量级上实现。
可以先22，然后44，直到全部排序完成
基数排序：
借助多关键字排序的思想对但逻辑关键字进行排序的方法。
小知识
P301算法时间复杂度比较
（1）借助于“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度为O(n*logn)
（2）当序列中的记录"基本有序"或n值较小时，它是最佳的排序方法
（3）稳定性是由方法本身决定的，对不稳定的排序方法而言，不管其描述形式如何，总能举出一个说明不稳定的实例来，反之，对稳定的排序方法，总能找到一种不引起不稳定的描述方式
