2.3-1:

   3 9 26 38 41 49 52 59

   3 26 41 52   9 38 49 57

3 41   52 26   38 57   9 49

3   41  52  26  38  57  9  49

2.3-2:(归并排序)

void mergeSort(int a[], int l, int r){    int m;    if(l < r)    {        m = (l + r) / 2;        mergeSort(a, l, m);        mergeSort(a, m+1, r);        merge(a, l, r, m);    }}void merge(int a[], int l, int r, int p){    int i, j, k;    int n1 = p - l + 1;    int n2 = r - p;    int lArray[n1], rArray[n2];    for(i=0; i
      
       = n2 || lArray[i] <= rArray[j]))        {            a[k] = lArray[i];            ++i;        }        else if(j < n2 && (i >= n1 || rArray[j] < lArray[i]))         {            a[k] = rArray[j];            ++j;        }    }}
      

2.3-3:

n=2:  Tn=2lg2=2

假设 n=k时等式成立

T_k+1=2(T_k) + 2^k+1=2 * (2^k * k) + 2^k+1=2^k+1(k+1)

2.3-4:

最差情况：

1   n=2;

T_n = T_n-1+n-1;

2.3-5:(二分查找)

int binarySearch(int a[], int v, int n){    int l, r, m;    l = 0;    r = n - 1;    while(l <= r)     {        m = (l + r) / 2;        if(v < a[m]) r = m - 1;        else if(v > a[m]) l = m + 1;        else return m;    }    return -1;}

最差情况：

2   n=2;

T_n=T(n/2) + 1      n=2^k;

θ(lgn)

2.3-6:

无法降低运行时间

2.3-7:(参考了网友的答案，做了一点优化，希望大家能提更好的改进建议）

算法：求一个N个数的集合是否含有和为X的2个元素(需要支持c99标准)

bool sumX(int a[], int n, int x){    int length, complement[n];    mergeSort(a, 0, n-1);    length = deduplication(a, n);    xComplement(a, complement, length, x);    return mergeSearch(a, complement, length);}bool mergeSearch(int a[], int b[], int n){    int i, j;    for(i=0, j=n-1; i
      
       =0 && a[i]!=b[j]; )        if(a[i] < b[j]) i++;        else j--;    return i
       
        =0;}void xComplement(int a[], int aComplement[], int n, int x){    int i;    for(i=0; i
        
          0 && a[i-1] != a[i]) j++;        tmp[j] = a[i];    }    for(i=0; i<=j; i++) a[i] = tmp[i];    return j+1;}void mergeSort(int a[], int l, int r){    int m;    if(l < r)    {        m = (l + r) / 2;        mergeSort(a, l, m);        mergeSort(a, m+1, r);        merge(a, l, r, m);    }}void merge(int a[], int l, int r, int m){    int max = 1000;    int i, j, k;    int n1 = m - l + 1;    int n2 = r - m;    int lArray[n1+1], rArray[n2+1];    for(i=0; i
        
       
      

θ(nlgn)