5个数排序所需的最少比较次数

若使用插入排序,最坏情况需要10次比较:1 + 2 + 3 + 4

若使用归并排序,最坏情况需要9次比较:nlogn

7次比较:

  1. 标记待排序元素为A,B,C,D,E。
  2. 先将A与B、C与D比较,假设A < B,C < D,再将A与C比较,不妨设A < C,则A < C < D,当前共3次比较。(若A > C,那就C < A < B,两种情况等价)
  3. 再将E折半插入A < C < D,最多需要2次比较(E先与C比较,若与C相等则只需1次比较,若小于C就再和A比较,若大于C就再和D比较)。
  4. 假设结果为A < C < D < E,再将B插入A < C < D < E,因为已有A < B,所以只需要将B插入C < D < E中,折半最多需要2次比较。