第二章算法基础

2.1 插入排序

template <class T>
void insertion_sort(T a[], int n) //n=a.length
{
    for (int j = 1; j < n; j++)
    {
        T key = a[j];
        int i = j - 1;
        while (i >= 0 && a[i] > key)
        {
            a[i + 1] = a[i];
            i = i - 1;
        }
        a[i + 1] = key;
    }
}

2.1-1

略

2.1-2

将第8行的>替换为<即可

template <class T>
void insertion_sort(T a[], int n) //n=a.length
{
    for (int j = 1; j < n; j++)
    {
        T key = a[j];
        int i = j - 1;
        while (i >= 0 && a[i] < key)
        {
            a[i + 1] = a[i];
            i = i - 1;
        }
        a[i + 1] = key;
    }
}

2.1-3

template <class T>
int find_in_array(T a[], T *&v, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (*v == a[i])
            return i;
    }
    v = nullptr;
    return -1;
}

2.1-4

void binary_add(int a[], int b[], int c[], int n)
{
    int jinwei = 0, sum = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        sum = a[i] + b[i] + jinwei;
        if (sum == 0)
            c[i + 1] = 0;
        if (sum == 1)
            c[i + 1] = 1;
        if (sum == 2)
        {
            c[i + 1] = 0;
            jinwei = 1;
        }
        if (sum == 3)
        {
            c[i + 1] = 1;
            jinwei = 1;
        }
    }
    c[0] = jinwei;

    return;
}

2.2 分析算法

2.2-1

$\Theta(n^3)$

2.2-2

选择排序

template <class T>
void selection_sort(T a[], int n)
{
    T temp;
    int minIndex = 0;
    for (int i = 0; i < n - 1; i++)
    {
        minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[minIndex] > a[j])
            {
                minIndex = j;
            }
        }
        temp = a[minIndex];
        a[minIndex] = a[i];
        a[i] = temp;
    }

    return;
}

最好情况：$\Theta(n^2)$

最坏情况：$\Theta(n^2)$

offical answer

2.2-3

平均需要检查$\frac{n}{2}$个元素，$\Theta(n)$

最坏情况需要检查$n$个元素,$\Theta(n)$

2.2-4

offical answer

2.3 设计算法

template <class T>
void merge(T a[], int start, int mid, int end)
{//将两个有序数组合并，无需哨兵
    int n1 = mid - start + 1;
    int n2 = end - mid - 1;
    T *L = new T[n1];
    T *R = new T[n2];
    for (int i = 0; i < n1; i++)
    {
        L[i] = a[start + i];
    }
    for (int j = 0; j < n2; j++)
    {
        R[j] = a[mid + j + 1];
    }
    int i = 0, j = 0;
    T m;
    for (int k = start; k < end; k++)
    {
        if (i < n1 && j < n2)
        {
            if (L[i] < R[j])
            {
                a[k] = L[i];
                m = a[k];
                i = i + 1;
            }
            else
            {
                a[k] = R[j];
                m = a[k];
                j = j + 1;
            }
        }
        else if (i < n1)
        {
            a[k] = L[i];
            i++;
        }
        else if (j < n2)
        {
            a[k] = R[j];
            j++;
        }
    }
    delete[] L;
    delete[] R;
}

template <class T>
void merge_sort(T a[], int end, int start = 0)
{//归并排序，对整个数组，start=0,r=a.length
    if (start < end - 1)
    {
        int mid = (start + end - 1) / 2;
        merge_sort(a, mid + 1, start);
        merge_sort(a, end, mid + 1);
        merge(a, start, mid, end);
    }
}

2.3-1、2.3-2、2.3-3

略

2.3-4

template <class T>
void insertion_sort_recursive(T a[], int n)
{
    if (n == 1)
    {
        return;
    }
    insertion_sort_recursive(a, n - 1);
    T key = a[n - 1];
    int i = n - 2;
    while (i >= 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i = i - 1;
    }
    a[i + 1] = key;

    return;
}

2.3-5

template <class T>
int binary_search_iterative(T a[], T v, int end, int start = 0)
{//二分查找的迭代版本，end最大为a中元素个数
    int mid = (end + start) / 2;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (v == a[mid])
            return mid;
        else if (v > a[mid])
        {
            start = mid + 1;
        }
        else
            end = mid - 1;
    }
    return -1;
}

template <class T>
int binary_search_recursive(T a[], T v, int end, int start = 0)
{//二分查找的递归版本，end最大为a中元素的个数
    if (start > end)
        return -1;
    int mid = (start + end) / 2;
    if (v == a[mid])
        return mid;
    else if (v > a[mid])
        return binary_search_recursive(a, v, end, mid + 1);
    else
        return binary_search_recursive(a, v, mid - 1, start);
}

2.3-6

不能，在最坏情况下，插入排序仍然需要移动$j-1$个元素，所以最坏情况总运行时间仍为$\Theta(n^2)$

2.3-7

template <class T>
bool find_two_elements_sum_x(T a[], T x, int n)
{//先对数组进行排序，再对x-a[i]进行二分查找
    merge_sort(a, 0, n - 1);
    int result = -1;
    for (int i = 0; i < n; i++)
    {
        result = binary_search_recursive(a, x - a[i], n, i + 1);
        if (result != -1)
            return true;
    }
    return false;
}

时间复杂度分析：

归并排序复杂度为$\Theta(nlgn)$

二分查找时间复杂度为$\Theta(lgn)$,最坏情况下执行n-1次，for循环时间复杂度为$\Theta(nlgn)$

最终时间复杂度为$\Theta(nlgn)+\Theta(nlgn)=\Theta(nlgn)$

章末思考题

2-1在归并排序中对小数组采用插入排序

a.

证明：长度为k的表最坏情况下需要$\Theta(k^2)$时间，则$\frac{n}{k}$个长度为k的表最坏情况下需要$\Theta(k^2\times{\frac{n}{k} })=\Theta(nk)$时间

b.

为了完成合并，每次将两个列表两两合并，再将结果两两合并，每次合并需要的时间为$\Theta(k\times{\frac{n}{k} })=\Theta(n)$时间，为了最终合成1个总表，需要$lg(\frac{n}{k})$次合并。所以，最坏情况下合并时间需要$\Theta(nlg(\frac{n}{k}))$

c.

标准的归并排序所需时间为$\Theta(nlgn)$，修改后的算法最坏情况运行时间为$\Theta(nk+nlg(\frac{n}{k}))$。

要使改进算法的时间与标准合并排序的时间相同，即使改进算法的时间不能出现$nlgn$的高阶项，易得，$nk$的阶数比$nlg(\frac{n}{k})$的阶数高，即$nk$的阶数不能高于$nlgn$，即k最大为$lgn$。

将$k=lgn$代入，得：$2nlgn-nlglgn$,忽略常数与低阶项，原式等于$nlgn$。

d.

在实践中，k应为插入排序比合并排序快的最大数组的长度。

2-2 冒泡排序的正确性

template <class T>
void bubble_sort(T a[], int end, int start = 0)
{//冒泡排序
    T temp;
    for (int i = start; i < end - 1; i++)
        for (int j = end - 1; j > i; j--)
        {
            if (a[j] < a[j - 1])
            {
                temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    return;
}

a.

需要证明$A’$中的元素对$A$中的元素完成了排列

b.

循环不变式：在里层的for循环每次迭代开始时，$A[j]=A[k]_{min},j\leq k\leq n-1$

初始化：最初，$j=n-1$，子数组$A[j..n-1]$中只有单个元素$A[n-1]$，循环不变式成立。

保持：考虑给定值j的迭代。根据循环不变式，$A[j]$是$A[j..n-1]$中的最小值。如果$A[j-1]$的值小于$A[j]$的值，则循环交换$A[j-1]$与$A[j]$的值，所以$A[j-1]$将会是$A[j-1..n-1]$中的最小值，则在下一次循环开始时，$j$减小，循环不变式依然成立。

终止：当$j=i$时循环终止，根据循环不变式，$A[i]=A[k]_{min},i\leq k\leq n-1$。

c.

循环不变式：在外层的for循环每次迭代开始时，子数组$A[0..i-1]$由数组$A[0..n-1]$中的i个排序好的最小值组成，并且子数组$A[i..n-1]$由最初在数组$A[0..n-1]$中的$n-i$个剩余值组成。

初始化：在循环的第一次迭代之前，$i=0$。子数组$A[0,i-1]$为空，循环不变式成立。

保持：考虑给定值$i$的迭代。根据循环不变式，$A[0..i-1]$由$A[1..n]$中的$i$个最小值按顺序排列组成。由(b)部分可得，在执行里层for循环之后，$A[i]$是$A[i..n-1]$中的最小值，因此$A[1..i]$现在是由$A[1..n]$中i个最小值的顺序排列。此外，由于里层for循环，子数组$A[i+1..n]$由剩余的$n-i-1$个值组成。

终止：当$i=n-1$时，外层for循环终止，因此$i-1=n-2$。根据循环不变性，$A[1..i-1]$即子数组$A[0..n-2]$，由最初的$A[0..n-1]$中的$n-1$个最小值顺序组成。则最后一个元素$A[n-1]$必须是最大值。因此，整个数组$A[0..n-1]$被排序。

d.

冒泡排序的最坏情况运行时间为$\Theta(n^2)$，与插入排序相同。

2-3 （霍纳(Horner)规则的正确性）

template <class T>
T horner(T a[], T x, int n)
{//霍纳规则
    T y = 0;
    for (int i = n; i >= 0; i--)
        y = a[i] + x * y;
    return y;
}

a.

$\Theta(n)$

b.

template <class T>
T naive_horner(T a[], T x, int n)
{//a中元素个数应为n+1
    T y = 0, temp = 1;
    for (int i = 0; i <= n; i++)
    {
        temp = 1;
        for (int j = 1; j <= i; j++)
            temp = temp * x;
        y += temp * a[i];
    }
    return y;
}

运行时间为$\Theta(n^2)$，性能不如霍纳规则。

c.

循环不变式：霍纳规则的每次for迭代开始时，都有

$y=\sum_{k=0}^{n-(i+1)}a_{k+i+1}x^k$

初始化：显然，第一次循环开始前，$i=n$，$y=0$。满足循环不变式。

保持：由for循环中的公式：

$\begin{align} y & = a_i + x \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k \\ & = a_i x^0 + \sum_{k = 0}^{n - i - 1} a_{k + i + 1} x^{k + 1} \\ & = a_i x^0 +\sum_{k = 1}^{n - i} a_{k + i} x^k \\ & = \sum_{k = 0}^{n - i} a_{k + i} x^k. \end{align}$

终止：循环结束时$i=-1$，可得

$y=\sum_{k=0}^{n-(i+1)}a_{k+i+1}x^k=\sum_{k=0}^na_kx^k$

d.

由循环不变式可的代码片段即为多项式的值。

2-4 逆序对

a.

<2 8="" ,3,="" ,6="" ,1="">

逆序对：(1,5),(2,5),(3,4),(3,5),(4,5)

b.

由大至小排列的拥有最多的逆序对，对每个$(i,j),1\leq i<j\leq n$，均为逆序对。逆序对的个数为$C_2^n=\frac{n(n-1)}{2}$。

c.

插入排序中每一次元素的移动，有对应着一个逆序对的消除。

d.

在归并排序的归并过程中，若后一半数组中的元素先排列到数组中，则存在前一半数组剩余元素个数个逆序对。

template <class T>
int merge_inversions(T a[], int start, int mid, int end)
{
    int inversions = 0;
    int n1 = mid - start + 1;
    int n2 = end - mid - 1;
    T *L = new T[n1];
    T *R = new T[n2];
    for (int i = 0; i < n1; i++)
    {
        L[i] = a[start + i];
    }
    for (int j = 0; j < n2; j++)
    {
        R[j] = a[mid + j + 1];
    }
    int i = 0, j = 0;
    T m;
    for (int k = start; k < end; k++)
    {
        if (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                a[k] = L[i];
                m = a[k];
                i = i + 1;
            }
            else
            {
                a[k] = R[j];
                m = a[k];
                inversions = inversions + n1 - i;
                j = j + 1;
            }
        }
        else if (i < n1)
        {
            a[k] = L[i];
            i++;
        }
        else if (j < n2)
        {
            a[k] = R[j];
            j++;
        }
    }
    delete[] L;
    delete[] R;
    return inversions;
}
template <class T>
int count_inversions(T a[], int end, int start = 0)
{//对整个数组，end=a.length
    int inversions = 0;
    if (start < end - 1)
    {
        int mid = (start + end - 1) / 2;
        inversions = inversions + count_inversions(a, mid + 1, start);
        inversions = inversions + count_inversions(a, end, mid + 1);
        inversions = inversions + merge_inversions(a, start, mid, end);
    }
    return inversions;
}

第二章 算法基础