选择排序是每次遍历剩余元素找到最小者,将其与当前元素交换。

选择排序的C实现:

void selection(int *n, int len)
{
    int i, j, k;
    for (i=0; i<len; i++) {
        k = i;
        for (j=i+1; j<len; j++) {
            if (*(n+j) < *(n+k)) {
                k = j;
            }
        }
        swap(n+i, n+k);
    }
}

选择排序的计算次数为\((n-1) + (n-2) + \cdots + 1 = n (n -1) / 2\) , 由此可知选择排序的时间复杂度为\(O(n^2)\) , 选择排序需要的额外空间为\(O(1)\) , 选择排序没有适应性,对任何情况都需要相同多的计算次数, 选择排序是不稳定的.

选择排序的优点是元素交换的次数较少,为\(O(n)\) , 因此在交换元素消耗较大的情况下可以选用。

comments powered by Disqus