编程珠玑总结—column 11 Sorting

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       

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)      

缺点：考虑到如果输入元素全部相等的情况,上面的算法退化为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)