首页 📖算法心得,文档剪藏

排序的定义

对某一序列对象根据某个关键字进行排序(一般是升序排序,降序排序只需要将升序排序序列逆序输出即可)。

排序相关术语

(1)稳定性
稳定的排序算法指的是,如果待排序序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。稳定性是实际业务中必须要考虑的因素。比如交易系统中,订单金额可能一样,但订单依然有时间上的先后顺序关系。
稳定排序:冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序
不稳定排序:选择排序、希尔排序、快速排序、堆排序
(2)比较类排序和非比较类排序
比较类排序:指的是需要通过大小比较来决定元素间的相对次序,由于其时间复杂度不能突破 O(nlogn),因此也称为“非线性时间”比较类排序;
非比较类排序:指的是不通过大小比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为“线性时间”非比较类排序。
比较类排序和非比较类排序
(3)时间复杂度
排序算法的时间复杂度指的是一个算法执行所耗费的时间,是对排序数据总的操作次数问题规模大小的一种度量。时间复杂度 O(f(n)) 反映当 n 变化时,操作次数呈现什么样的规律。
分析排序算法的时间复杂度时,要分别给出最好情况、最坏情况、平均情况下的时间复杂度。这样做,一是便于各种排序算法的对比分析,二是待排序数据有的接近有序而有的则完全无序,我们需要知道排序算法在不同数据环境下的性能表现,从而能够在不同的场景下选择更加适合的排序算法。
(4)空间复杂度 <内部排序、外部排序>
指算法在计算机内执行时所需存储空间的度量,它也是数据规模 n 的函数。由于待排序的记录数量不同,使得排序过程中涉及的存储器需求不同,可将排序方法分为两大类:内部排序与外部排序。
内部排序(Sorted In-Place):只利用存储待排序数据的存储空间进行比较和交换,排序过程只发生在主存中,也称“原地排序” 。
外部排序(Sorted Out-Place):待排序数据的数量很大,无法一次全部装入主存,需要在主存和外存之间进行多次数据交换,以达到排序所有数据的目的,也称“非原地排序”。
各类算法各项性能比较
(5)有序度、逆序度、满有序度
有序度:待排序数据序列有序的程度。待排序序列中,如果下标 i<j,有a[i]<a[j],称为有序度;
逆序度:待排序数据序列无序的程度。待排序序列中,如果下标 i<j,有a[i]>a[j],称为逆序度;
满有序度:待排序数据序列中,如果有序度达到 n(n-1)/2,称为满有序度,此时待排序数据序列是完全有序的。
满有序度值 n(n-1)/2 的推导(利用排列、组合知识):

因此,当待排序数据序列有 n 个元素,如果有序度等于每两个元素的组合数n(n-1)/2,那么该待排序序列其实是有序的,这就是满有序度的概念。
举例:
数据序列 2,3,4,5,6,7 中,n=6,n(n-1)/2=15。说明该序列共有 15 种组合,如下所示:
(2,3)(2,4)(2,5)(2,6)(2,7) --- 5 种
(3,4)(3,5)(3,6)(3,7) --- 4 种
(4,5)(4,6)(4,7) --- 3 种
(5,6)(5,7) --- 2 种
(6,7) --- 1 种
每个组合均满足当下标 i<j 时,a[i]<a[j] 的要求,说明以上数据序列已是有序序列。



文章评论

目录