以下是选择排序的伪代码以及一些分析:

SELECTION-SORT(A)                         执行次数

1   for j = 1 to Length(A)                              n

2       i = j                                                          n

3       key = A(i)                                               n  

4       for i to Lenth(A)                                    n(n+1)/2

5           if key>A(i)                                          ...

6                 key = A(i)                                     ...

7                 k = i                                               ...

8        A(k) = A(j)                                             ...

9        A(j)  = key                                             ...

 

   所以run time is O(n*n)

转载自“5年的救赎” 博客
------------------------------------------------------------

SELECTION-SORT(A)

 　　for i←1 to n-1

  　　　　do min←∞                        //此处它定义min为无穷大有何作用呢？

                               这里主要是为了找到最小值，

                              就是找个最小值，找到比min小就交换
　　　　　　for j←i to n
　　　　　　　　　 do if A[i]<min

    　　　　　　　　    then min←A[j]

    　　　　　　　　    minlabel←j



 　　exchange A[i]↔A[minlabel]

[问题2] 循环不变式：

初始化：此时i=1，而子数组A[1..i]。亦即，它只包含一个元素A[1]，显然是已排序的。

保持：在第二个for循环体中，即从A[i]到A[n]的数组元素中选出一个最小的，与第i个元素即A[i]互相交换相应的值，此时，因为假设已知A[1..i-1]已经排序好了，而新选出来的也同时大于A[i..i-1]中的任何一个数，这就是说A[1..i]也已排序。

终止：当i=n-1时，第二个for循环，从A[n-1]和A[n]中选出一个较小的与A[n-1]进行值交换。之后，所有的元素也就排序完了。

[问题3] 因为当i=n-1时，第二个for循环遍历的就只有A[n-1]和A[n]两个元素了，从中选出较小的那个数与A[i]值交换后被放到了最后第二位，而较大的那个数（同时也是全部元素中最大的），则自然排到了最后一位。显然已满足排序要求。

[问题4] 最佳和最坏情况下的运行时间都为Θ(n²)。因为这种直接选择排序，其关键字的比较次数与各元素原来的排列顺序无关。

转载自http://www.cnblogs.com/timebug/archive/2010/03/10/1682880.html