文件局部有序或文件长度较小的情况下,最佳的排序方法是什么-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

文件局部有序或文件长度较小的情况下,最佳的排序方法是什么

知与谁同 2018-07-21 16:45:01 792
文件局部有序或文件长度较小的情况下,最佳的排序方法是什么
分享到
取消 提交回答
全部回答(3)
  • 沉默术士
    2019-07-17 22:51:02
    直接插入排序
    0 0
  • 寒凝雪
    2019-07-17 22:51:02
    我觉得多会还是冒泡法比较好用了.
    0 0
  • 知与谁同
    2019-07-17 22:51:02
    直接插入排序。
    当待排序列基本有序时,对冒泡排序来说,若最大关键字位于序列首部,则每趟排序仅能使其“下沉”一个位置,要使其下沉到底部仍需n-1趟排序,也即时间复杂度仍为O(n^2)。而对简单选择排序来说,其比较次数与待排序列的初始状态无关;归并排序要求待排序列已经部分有序,而部分有序的含义是待排序列由若干有序的子序列组成,即每个子序列必须有序,并且其时间复杂度为O(n log2n);直接插入排序在待排序列基本有序时,每趟的比较次数大为降低,也即n-1趟比较的时间复杂度由O(n^2)降至O(n)。

    各种排序方法的选择:
    ①就平均时间性能而言,快速排序最佳,其所需时间最省,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当n较大时,归并排序较堆排序省,但归并排序所需的辅助空间最大。
    ②简单排序方法中,直接插入排序最简单,当待排序的结点已按键值“基本有序”且n较小时,则应采用直接插入排序或冒泡排序,直接插入排序比冒泡排序更快些,因此经常将直接插入排序和其他的排序方法结合在一起使用。
    ③当n很大且键值位数较小时,采用基数排序较好;而当键值的最高位分布较均匀时,可先按其最高位将待排序结点分成若干子表,而后对各子表进行直接插入排序。
    ④从方法的稳定性来比较,直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法;而直接选择排序、希尔排序、堆排序和快速排序都是不稳定的排序方法。

    内部排序方法的选择:
    各种排序方法各有优缺点,故在不同情况下可作不同的选择。通常需考虑的因素有:待排序的记录个数;记录本身的大小;记录的键值分布情况等。
    *若待排序的记录个数n较小时,可采用简单排序方法
    *若n 较大时,应采用快速排序或堆排序。
    若待排序的记录已基本有序,可采用起泡排序。
    0 0
添加回答
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

推荐文章