Technorati 标签:
算法,
笔记
插入排序：
1: for i = [1,n)
2: for (j = i; j>0 && x[j-1]>x[j]; j--)
3: swap(j-1, j)
1: for i = [1, n)
2: t = x[i]
3: for (j=i; j>0 && x[j-1]>x[j]; j--)
4: x[j] = x[j-1];
5: x[j] = t;
快速排序：
方法一：（维持循环不变量）
| t |
| >=t | ? |
| l | m | i u |
1: void qsort1(l, u)
2: if l>=u
3: return
4: m = l
5: for i=[l+1, u]
6: /* invariant:x[l+1...m] < x[l] &&
7: x[m+1...u] >= x[l]*/
8: if x[i]
9: swap(++m, i)
10: swap(l, m)
11: qsort1(l, m-1)
12: qsort1(m+1, u)
13:
缺点：考虑到如果输入元素全部相等的情况,上面的算法退化为O(N^2)，所以使用下面的算法
方法二（从数组的两端开始扫描）：
1: void qsort3(l, u)
2: if l>=u
3: return
4: t = [l]; i=l; j=u+1;
5: loop:
6: do i++ while i<=u && x[i]
7: do j-- while x[j]>t;
8: if i>j
9: break;
10: swap(i, j)
11: swap(l, j)
12: qsort3(l, j-1)
13: qsort3(j+1, u)
优化，考虑到小数组的情况下，插入排序效率更高，结合qsort3与isort3得到qsort4
1: void qsort4(l, u)
2: if l-u <= cutoff
3: return ;
4: t = x[l]; i=l; j=u+1;
5: loop:
6: do i++; while i<=u && x[i]
7: do j--; while x[i]>t;
8: if i>j
9: break;
10: temp = x[i]; x[i] = x[j]; x[j]=temp;
11: swap(l, j)
12: qsort4(l, j-1)
13: qsort4(j+1, u)
