两年后再来跟我扯 选择排序

上次漏了说一个 选择排序的要点， 对于查找第 k 小的数， 如果 k很小， 用选择排序选择，
时间复杂度为 Nk, 近乎线性， 别再抱着快速排序不放了...

呵呵，版主有点欺人了。。。

不小心多回复了一个，麻烦版主帮我删掉一个。谢了。。。

void selection_sort(void)
{
        int i, j, min, temp;

        for (i = 0; i < LEN; i++) {
                for (j = min = i; j < LEN; j++)
                        if (a[min] > a[j])
                                min = j;          c1
                temp = a[min];                    c2
                a[min] = a[i];                    c3
                a[i] = temp;                      c4
        }
}
首先分析最坏情况：
设n=LEN，m为内层循环执行次数。
可得：
总的执行时间=(n-1)*(c2+c3+c4)+m*c1 （1）
然后我们把m写成n的函数：
根据经验，可得：
m=n(n+1)/2
代入（1）中，一眼就可以看出来可以表示成an^2+bn+c的形式（注意n(n+1)算出来本身就已经出现二次项了），是n的二次函数。
所以最坏情况下选择排序的时间复杂度为Θ(n^2)。
同理，平均情况下选择排序的时间复杂度为Θ(n^2)。
最好情况：
序列已经排好序。
但外层和内层循环还是会执行，所以最好情况下选择排序的时间复杂度依然为Θ(n^2)。
可以看出，选择排序分不出最坏、平均、最好情况，它的时间复杂度是固定的。
所以选择排序的时间复杂度为O(n^2)。

                            bangmangding

恩， 可以。
不过我看你写的代码， 就不愿意和你讨论算法。

又有点欺人了。。。
不讨论那算了。

学习中