2020年5月

《算法(第4版)》笔记

归并

归并排序基于“归并”这个简单的操作,即将两个有序的数组归并成一个更大的有序数组。

要将一个数组排序,可以先(递归地)将它分成两半分别排序,然后将结果归并起来。

// c++
template<class T>
void merge(T& a, int lo, int mid, int hi, T& aux)
{
    // 将a[lo .. mid]和a[mid+1 .. hi]归并
    int i = lo;
    int j = mid + 1;

    for (int k=lo; k<=hi; ++k)
        aux[k] = a[k];

    for (int k=lo; k<=hi; ++k)
    {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (aux[j] < aux[i])
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

- 阅读剩余部分 -

《算法(第4版)》笔记

选择排序

首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法叫做选择排序,因为它在不断地选择剩余元素之中的最小者。

选择排序的缺点:一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长。

// c++
// 将容器a按升序排列
template<class T>
void selection_sort(T& a)
{
    int n = a.size();
    for (int i=0; i<n; ++i)
    {
        int min = i;
        for (int j=i+1; j<n; ++j)
        {
            if (a[j] < a[min])
                min = j;
        }

        std::swap(a[i], a[min]);
    }
}

- 阅读剩余部分 -