排序想法

• 选择排序相当于浪费了（一遍遍历时）很多次比较带来的隐性信息，比如，a（被放弃的假max）虽然没有真max大，但他比让他成为假max的那些量大，他应该放在这些量的右边。但是选择排序并没有利用这个信息，而是反复比较。
  （不过选择排序的移动是精确的。没有中途的步数。）
  一共有C(2,n)=n!/2！=n!/2条关系，他一遍只梳理了n条。（即，确定一个元素的位置，需要知道一个n条关系，例如a>*1,a>*2,a>*3 ; a<*5,a<*6,a<*7 可以知道a在***a***这个位置。而不需要知道***与***内部的关系。（不过这个和7>6>5>4>a>3>2>1不一样,这样的”链条”包含了嵌套的关系。因为不等号有方向性，而不是像等号那样，分开写和链条式写法等效）（每一遍梳理的是每条关于max的n条关系，于是可以确定max的位置）
  

• 冒泡排序适当修正了这一点。即，假max的位置有被放置在假max基底的之后，真max的之前。可以理解为，冒泡排序为一遍就执行了把整个序列以假max划分的好几个嵌套序列的选择排序。排了一遍后的结果是这样：(((((((***)小小假max**)小假max****)假max***)真max) (任何max比他左大括号内的都大）

  但是 例如 3 1 4 2→1 3 4 2→1 3 2 4 或者 3 1 0 2→1 3 0 2→1 0 3 2→1 0 2 3 一共有C(2,n)=n!/2！=n!/2条关系
  但是他对于每个假max的与左边元素关系的相对位置都放置对了。也就是说，他一遍的有效梳理量取决于假max的数量和位置安排。 最小为n（真max放在最开始），最大为n!/2，即所有关系，即一开始就排好了。
  

  移动情况为 与比较性能有关。即比出一次true情况就要移动一次（更。。多？）

• 而快速排序 一遍可以得到的信息是，左边的n/2个元素和右边的n/2个元素一一的关系，即n**2/4.当n>4时，性能就比上两个好。再下一遍比较，得到的信息是2*（(n/2/2)**2）=2*(n**2/16)=n**2/8

  移动情况同冒泡（更。。少？）。即比出一次true情况就要移动一次

• 二分法的妙处：
  例如，当要把7插入1 2 3 4 5 6 8 9 10中时，如果是从右开始依次比较，则每一次只能获取到一个信息，即，比新的右边的一个大。（1 2 3 4 5 6 8 9 10 7→1 2 3 4 5 6 8 9 7 10→1 2 3 4 5 6 8 7 9 10 目前只获得了两个信息） ，要直到到达位置时，才能突然获得（该数字-1）条关系。即，这个排序很靠运气。需要离边缘，并且是起始比较的那一头很近，才有好效果。
  

  但如果是从中间开始比，就可以稳定获得n/2个关系 1 2 3 4 5 7 6 8 9 10即，我比左边的n/2个加右边的一个都大（或者反过来）。下一次比较可以获得n/4个关系。

  即，要利用好原排序本来就提供了的关系。

• 归并排序相当于将冒泡排序的无效比较给生效了（？

我建议，插入排序优化为 每次循环的插入时，使用二分法（快速排序？）找到位置！

• 作业尝试↑

Q：排序算法稳定性在什么情况下是必需的？

A：在现实中，我们有可能基于对象的某个属性进行排序。例如，学生有姓名和身高两个属性，我们希望实现一个多级排序：先按照姓名进行排序，得到 (A, 180) (B, 185) (C, 170) (D, 170) ；再对身高进行排序。由于排序算法不稳定，因此可能得到 (D, 170) (C, 170) (A, 180) (B, 185) 。