常见的分为8种:(名称 平均情况时间复杂度 空间复杂度)
直接插入 O(n平方) O(1)
希尔排序 O(n1.3次方) O(1)
直接排序 O(n平方) O(1)
堆排序 O(nlog2n) O(1)
冒泡排序 O(n2) O(n平方)
快速排序 O(nlog2n) O(nlog2n)
归并排序 O(nlog2n) O(n)
基数排序 O(d(r+n)) O(rd+n)
这是具体的8中方法的时间复杂度和空间复杂度表。但是,具体情况具体具体分析。如果待排记录的个数n较小,则可采用直接插入排序或折半插入排序 。如果待排记录的个数n较大,应该选择时间复杂度为O(nln(n))的排序方法,如快 速排序,堆排序或归并排序。 快速排序是处理大量数据的最好方法。当待排序序列的关键字是随机分布时,快速排序的平均时间复杂度最优,但是在待排序序列基本有序时,将蜕化为冒泡排序,其时间性能将不如堆排序或归并排序。 堆排序所需的辅助空间少于快速排序,并且在最坏的情况下时间复杂度不会变化。 归并排序所需的时间比堆排序省,但是它所需的辅助存储空间最多 。 快速排序、堆排序、希尔排序和直接选择排序都是不稳定的排序法,直接插入排序 法、冒泡排序法、归并排序法都是稳定的排序法。 如果待排序列记录的厨师状态已按关键字基本有序,则选择直接插入排序或冒泡排 序。 |