[TOC]

插入排序

纸牌游戏，为将数组x[n]按升序排序，首先将第一个元素视为有序子数组x[0..0],然后插入x[1],x[2],x[n-1]

1. isort1 调用系统的库函数swap

for i = [1,n)
      for   (j = i; j > 0 && x[j - 1] > x[j]; j --)
                swap(j - 1,j)

2. isort2 把swap函数的函数体内联写入内循环实现程序的加速，time(isort2) ~ 1/3 time(isort1)；

for i = [1,n)
      for   (j = i; j > 0 && x[j - 1] > x[j]; j --)
      {    t = x[j]; x[j] = x[j - 1];x[j - 1] = t;  }

3. isort3 将含有t的赋值语句移除内循环，并相应的修改比较语句，得到isort3比isort2快15 %；

for i = [1,n)
      t = x[i]
      for   (j = i; j > 0 && x[j - 1] > t; j --)
             x[j] = x[j - 1];
      x[j] = t;

快速排序

思想：在数组中找一个数，然后按这个数进行划分，大于该数的放到左边，小于该数的放在右边。如下图：按t的值划分，[a,m]小于t,[m+1,i-1] >=t ,[i,b]等待划分。

分别用下表l和u表示数组待排序部分的下界和上界，递归结束的条件是待排序部分的元素个数小于2。

void qsort(l,u)
          if    l >= u    then
                return
          qsort(l,p-1)
          qsort(p+1,u)

优化角度

1. 展开系统的swap函数
2. 双向划分（n个相同元素组成的数组）
3. 随机选择划分元素
4. 在小子数组上采用其他方式进行排序（如插入排序）

1.qsort1

• 依据l处的值，对[l+1,u]进行从左往右进行划分。划分好之后，[l,l+1,m,u],再交换l 与 m处的值。

void qsort1(l,u)
          if   (l > u) return
          m = l
          for i=[l + 1,u]
          if (x[i] < x[l])   
              swap(++m,i)
         swap(l,m)
         qsort1(l,m - 1)
         qsort1(m + 1,u)

2.qsort2,对qsrot1的稍微修改

• 依据l处的值，对[l,u]进行从右往左进行划分。划分好之后，[l,m,u],l处的值作为哨兵。

void qsort2(l,u)
          if   (l > u) return
          m = u + 1 
          for i=[u,l] //(i = u ; i >= l ;i --)
          if (x[i] >= x[l])   
              swap(--m,i)
              
         qsort2(l,m - 1)
         qsort2(m + 1,u)

3.qsort3

• 双向划分i从l递增,j从u递减

void qsort3(l,u)
    if (l >= u) return // 此处修改为 if (u - l < cutoff) return
    // 此处插入，改进思路1，可进行优化
    t = x[l]; i = l ;j = u + 1 ;
    loop
        do i++ while i <= u && x[i] < t
        do j-- while x[j] > t
        if i > j
            break;
        swap(i,j)
    swap(l,j)
    qsort3(l,j-1)
    qsort3(j+1,u)

//改进思路2
qsort3(0,n-1)
isort3()

• qsort3的改进思路
  1. 随机选择划分元素，swap(x[l],randint(l,u)),randint(l,u)产生的数为[l,u]
  2. 在小的子数组上调用快速排序，（如 u - l < cutoff时不执行任何操作，cutoff是一个小整数），程序结束时，数组并不是有序的，而是被组合成一块一块随机排列的值，并且满足这样的条件：某一块中的元素小于它右边任何块中的元素，通过另一种排序算法对块内部进行排序。由于数组几乎是有序的，因此插入排序比较适用。
  3. 1和2的改进思路同时使用。

4.qsort4

• 展开循环体内swap函数的代码，得到快速排序的最终代码

void qsort4(l,u)
    if u - l < cutoff
        return
    // 此处插入，改进思路1，可进行优化
    swap(1,randint(l,u))
    t = x[l]; i = l ;j = u + 1 ;
    loop
        do i++ while i <= u && x[i] < t
        do j-- while x[j] > t
        if i > j
            break;
        temp = x[i]; x[i] = x[j]; x[j] = temp;
    swap(l,j)
    qsort3(l,j-1)
    qsort3(j+1,u)

qsort4(0,n-1);
isort3();