排序算法的性能由算法的时间和空间确定的，而时间又是由比较和移动的次数确定的。若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素为正序。反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表中元素为反序。6/69
排序算法的性能由算法的时间和空间确定的，而时间又是由比较 和移动的次数确定的。 若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素 为正序。 反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表 中元素为反序。 6/69
基于比较的排序算法的下界n=3的决策树(R1,R2,R3)k1≤k2(R1,R2,Rg)(R2,R1,R3)k,≤k3ki≤k3是是否否V①④(R1,R3,R2)(R2,R3,R1)k≤k3k,≤k3(Ri,R2,Rg)(R2,R1,R,)是是否否③5?(R1,R3,R2)(R3,R1,R2)(R2,R3,R1)(R3,R2,R1)正序不变，逆序交换！3！=6个叶子结点7/69
(R3,R1,R2) (R3,R2,R1) (R2,R3,R1) (R2,R1,R3) (R1,R3,R2) 是 否 (R1,R2,R3) k1≤k2 k2≤k3 ① k1≤k3 ② ③ 是 否 是 否 k1≤k3 ④ k2≤k3 ⑤ ⑥ 是 否 (R1,R2,R3) (R1,R2,R3) (R1,R3,R2) (R2,R1,R3) (R2,R3,R1) n=3的决策树 正序不变，逆序交换！ 3!=6个叶子结点 7/69
推广一下，对于n个元素排序结果有n!种情况，对应的决策树是一棵有n！个叶子结点的二叉树。设其高度为h，其中没有单分支结点，总结点个数=2n！-1，其高度等同于含2n!-1个结点的完全二叉树的高度，则h=1og2(2n!)=1og2n!+1，而1og2n!=nlog2n，即h=o(nlog2n)。由此推出n个元素的序列采用基于比较的排序方法最坏情况需要o(nlog2n)次关键字比较，移动次数也是同样的数量级。基于比较的排序算法的下界为o(nlog,n)，同样可以证明平均时间复杂度也为o(nlog2n)。8/69
推广一下，对于n个元素排序结果有n!种情况，对应的决策树是一棵有n! 个叶子结点的二叉树。 设其高度为h，其中没有单分支结点，总结点个数=2n!-1，其高度等同于 含2n!-1个结点的完全二叉树的高度，则h=log2(2n!)= log2n!+1，而 log2n!≈nlog2n，即h=O(nlog2n)。 由此推出n个元素的序列采用基于比较的排序方法最坏情况需要O(nlog2n) 次关键字比较，移动次数也是同样的数量级。 基于比较的排序算法的下界为O(nlog2n)，同样可以证明平均时间复杂度 也为O(nlog2n)。 8/69
5.排序的稳定性当待排序元素的关键字均不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。如果待排序的表中，存在有多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。9/69
5. 排序的稳定性 当待排序元素的关键字均不相同时，排序的结果是唯一的，否则排 序的结果不一定唯一。 如果待排序的表中，存在有多个关键字相同的元素，经过排序后这 些具有相同关键字的元素之间的相对次序保持不变，则称这种排序 方法是稳定的。 反之，若具有相同关键字的元素之间的相对次序发生变化，则称这 种排序方法是不稳定的。 9/69
6.排序数据的组织以顺序表作为排序数据的存储结构（除基数排序采用单链表外）。假设关键字为int类型。待排序的顺序表中元素类型如下：//顺序表元素类型class RecType//存放关键字，假设关键字为int类型( int key;1/存放其他数据，假设为String类型String data;1/构造方法publicRecType(int d){ key=d;}10/69
以顺序表作为排序数据的存储结构（除基数排序采用单链表外）。 假设关键字为int类型。待排序的顺序表中元素类型如下： class RecType //顺序表元素类型 { int key; //存放关键字，假设关键字为int类型 String data; //存放其他数据，假设为String类型 public RecType(int d) //构造方法 { key=d; } } 6. 排序数据的组织 10/69