关于排序方法的简单总结。
1.稳定性：
假设记录中存在两个关键字相等的记录，若排序后两个记录的顺序不变，则所用的排序方法是稳定的，若可能使排序后的序列中两个记录的顺序变化，则方法是不稳定的。
2.内部排序和外部排序：
内部排序指的是待排序记录存放在计算机随机储存器中进行的排序过程；
外部排序指的是待排序记录数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
3.常用的五大类内部排序：
插入（直接插入、希尔等）、交换（起泡、快速等）、选择（直接选择、堆排序等）、归并、基数排序。
4.直接插入排序：
基本操作：将一个记录插入到已排好序的有序表中
稳定性：稳定
时间复杂度：O(n^2)
空间复杂度：O(1)
5.起泡排序：
基本操作：将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个和第三个记录的关键字，依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟起泡排序，……
稳定性：稳定
时间复杂度：O(n^2)
空间复杂度：O(1)
6.快速排序：
基本操作：附设两个指针low和high，它们的初值分别为low和high，设枢轴（一般选为第一个记录）记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。算法如下图所示：
稳定性：不稳定
时间复杂度：O(nlogn)
空间复杂度：O(logn)
7.归并排序：
基本操作：将两个或两个以上的有序表组合成一个有序表。两两归并，再两两归并，……
具体过程见下图：
稳定性：稳定
时间复杂度：O(nlogn)
空间复杂度：O(n)
8.基数排序：
借助多关键字排序的思想对单逻辑关键字进行排序
时间复杂度：O(n)
空间复杂度：O(1)
9.堆排序：
大根堆、小根堆
时间复杂度：O(nlogn)
空间复杂度：O(1)
10.从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。
从方法的稳定性来比较，基数排序是稳定的内排方法，然而，快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。
直接插入排序最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法。