的排序方法中采用哪种方法最好

发布于:2019-05-28   编辑:admin 浏览:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  我们通常所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。

  一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。

  另一种是非比较排序,时间复杂度可以达到O(n),主要有:计数排序,基数排序,桶排序等。

  排序算法稳定性的简单形式化定义为:如果Ai = Aj,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。

  对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法进行分析从而得到稳定的特性。需要注意的是,排序算法是否为稳定的是由具体算法决定的,不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。

  例如,对于冒泡排序,原本是稳定的排序算法,如果将记录交换的条件改成A[i] = A[i + 1],则两个相等的记录就会交换位置,从而变成不稳定的排序算法。