时间复杂度
- (1)直接插入、直接选择、冒泡排序算法的时间复杂度为O (n2)。
- (2)快速、归并、堆排序算法的时间复杂度为O(nlog2n)。
- (3)希尔排序算法的时间复杂度很难计算，有几种较接近的答案:O(nlog2n)或O(n1.25)。
- (4)基数排序算法的时间复杂度为O(d* (rd+n))，其中rd是基数，d是关键字的位数，n是元素个数。
稳定性
- (1)直接插入、冒泡、归并和基数排序算法是稳定的;
- (2)直接选择、希尔、快速和堆排序算法是不稳定的。
辅助空间(空间复杂度)
- (1)直接插入、直接选择、冒泡、希尔和堆排序算法需要辅助空间为O(1)。
- (2)快速排序算法需要辅助空间为O(log2n);
- (3)归并排序算法需要辅助空间为O(n)；
- (4)基数排序算法需要辅助空间为O(n+rd) 。
选取排序方法时需要考虑的主要因素
- (1)待排序的记录个数。
- (2)记录本身的大小和存储结构。
- (3)关键字的分布情况。
- (4)对排序稳定性的要求。
- (5)时间和空间复杂度等。
排序方法的选取
- (1)若待排序的一组记录数目较小(如n≤50）时，可采用插入排序或选择排序。
- (2)若n较大时，则应采用快速排序、堆排序或归并排序。
- (3)若待排序记录按关键字基本有序时，则适宜选用直接插入排序或冒泡排序。
- (4)当n很大，而且关键字位数较少时，采用链式基数排序较好。
- (5)关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。
排序方法对记录存储方式的要求
一般的排序方法都可以在顺序结构（一维数组）上实现。当记录本身信息量较大时，为了避免移动记录耗费大量的时间，可以来用链式存储结构。例如：插入排序、归并排序、基数排序易于在链表上实现，使之减少记录的移动次数，但有的排序方法，如：快速排序、堆排序在链表上却难于实现，在这种请况下，可以提取关键字建立索引表，然后对索引表进行排序。