一、内部排序方法：
①插入排序类：
（1）直接插入排序 （2）折半插入排序 （3）2-路插入排序（4）表插入排序（5）希尔排序
（稳定的排序）O(n2) （不稳定的排序）
②交换排序类：
（1）划分算法+快速排序 （2）冒泡排序
（不稳定的排序）O(nlogn)最坏情况：已经排好序 （稳定的排序）最坏情况下，比较次数为n(n-1)/2
③选择排序类：
（不稳定的排序）O(n2) （不稳定的排序）O(nlogn)
简单选择排序比较次数：O(n*n) 移动次数：O(n)
④归并排序类：
（1）合并两个已排序表+自底向上归并排序 （2）自顶向上合并排序
（稳定的排序）O(nlogn)
⑤基数排序
（1）多关键字排序（2）链式基数排序
（稳定的排序）O（d（n+rd））也可以写成O（d·n）
适用于n值很大而关键字较小的序列。若关健字大，而序列中“最高位关键字”均不同，可以先“最高关键字”变成小序列后直接插入排序。
元素移动次数和关键字初始排序无关。
⑥其他排序
枚举排序（计数排序）
二、各种排序算法比较：
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不一定？ |
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn)~O(n) | 不稳定 |
| 基数排序 | O(d*(n+rd)) | O(d*(n+rd)) | O(d*(n+rd)) | O(rd) | 稳定 |
从算法的简单性来看：
简单算法：冒泡、简单选择、直接插入、基数
改进算法：希尔、堆、归并、快速
从平均情况来看：
堆归并，归并，快速都为O(nlogn) 胜过 希尔排序O(nlogn)~O(n2) 胜过 冒泡，简单选择，直接插入
O(nlogn) ：（1）快速排序 （2）堆排序 （3）归并排序 ， 平均下速度：堆 > 快速 > 归并 O(nlogn)~O(n2)：（1）希尔排序 ， 因dlta增量序列变化复杂度变化：O(n2) ：（1）直接插入排序 （2）冒泡排序 （3）简单选择排序 O(d*(n+rd)) ：（1）基数排序
最好情况来看：
冒泡，直接插入O(n) 更优。即如果待排序序列总是基本有序，那么反而不应该考虑4种复杂的改进算法
最快情况来看：
堆排序、归并排序O(nlogn) 胜过 快速排序，及其他O(n2)
时间复杂度：
归并排序 和 堆排序 发挥稳定； 快速排序 时好时坏 ；冒泡排序 和 直接插入排序 在简单的，基本有序下表现好
稳定性：（一对数字不进行两次和两次以上比较）
稳定的排序：（1）冒泡排序（2）直接插入排序（3）归并排序（4）基数排序
不稳定的排序：（1）希尔排序（2）快速排序（3）堆排序
不一定：简单选择排序
具体介绍（介绍传送门）
从待排序记录个数上： 待排序个数 n 越小，简单排序更适合。 n 越大，改进的排序方法更适合。
下表给出了当n的值在500到5000之间时，5种排序算法的平均比较次数的实验结果
选择排序 插入排序 自底向上归并 自顶向下归并 快速排序
| n | SelectionSort | InsertionSort | BottomUpSort | MergeSort | QuickSort |
| 500 | 124 750 | 62 747 | 3852 | 3852 | 6291 |
| 1000 | 499 500 | 261 260 | 8682 | 8704 | 15 693 |
| 1500 | 1 124 250 | 566 627 | 14 085 | 13 984 | 28 172 |
| 2000 | 1 999 000 | 1 000 488 | 19 393 | 19 426 | 34 020 |
| 2500 | 3 123 750 | 1 564 522 | 25 951 | 25 111 | 52 513 |
| 3000 | 4 498 500 | 2 251 112 | 31 241 | 30 930 | 55 397 |
| 3500 | 6 123 250 | 3 088 971 | 37 102 | 36 762 | 67 131 |
| 4000 | 7 998 000 | 4 042 842 | 42 882 | 42 859 | 79 432 |
| 4500 | 10 122 750 | 5 103 513 | 51 615 | 49 071 | 98 635 |
| 5000 | 12 497 500 | 6 180 358 | 56 888 | 55 280 | 106 178 |
综合来看，快速排序是性能最好的排序，，但不同场合我们要考虑不同的算法来应对。