Articles

选择排序(Selection Sort)

Introduction to Algorithms这本书在习题2.2-2中提到了选择排序,The Algorithm Design Manual这本书中2.5.1节介绍了选择排序。选择排序的想法比较直观,首先在集合中选择一个最小的元素,然后在剩下的元素中选择一个次小的,以此类推。与插入排序相比,选择排序进行元素比较的次数要稍微多一些,元素交换的次数则要少一些。

template <typename T>
void swap(T &l, T &r)
{
    T tmp = l;
    l = r;
    r = tmp;
}

template
void selection_sort(T a[], int length)
{
    for (int i = 0; i < length; i++)
    {
        int min = i;
        for (int j = i + 1; j < length; j++)
            if (a[j] < a[min])
                min = j;
        swap(a[i], a[min]);
    }
}

选择排序在最坏的情况下时间复杂度是\( O(n^2) \),空间复杂度是\( O(1) \)。