各排序算法的复杂度 内部排序和外部排序 内部排序,指的是待排序的几率存放在计算机随机存储器中进行的排序过程; 外部排序,指的是排序中要对外存储器进行访问的排序过程。 归并排序需要外部数组进行存储,来存放对半分隔的临时数组,所以是外部排序。
不稳定算法 稳定排序:若在待排序的记录中,存在两个或两个以上的关键码值相等的记录,经排序后这些记录的相对次序仍然保持不变,则称相应的排序方法是稳定的方法,否则是不稳定的方法。
判断算法是否稳定主要是看算法是否比较相邻元素,交换相邻元素,如果一个算法既比较相邻元素,又交换相邻元素,那么相等的元素不会彼此进行交换,那么相对次序永远不会变。
例如针对于数组 [5,….,5],第一个 5 排在第二个 5 前面,那么当序列变为 […,5,5…] 时,两个 5 之间不会交换位置,那么相对次序肯定就不会变了,所以算法稳定。
堆排序比较的不是相邻元素,也不是交换相邻元素,所以不稳定。
快排比较的是相邻的元素,但是交换的不是相邻元素,所以不稳定。
选择排序比较的不是相邻元素,也不是交换相邻元素,所以不稳定。
希尔排序比较的不是相邻元素,也不是交换相邻元素,所以不稳定。
所以不稳定算法有: