程式設計珠玑總結—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)