选择排序算法伪代码2.2-2中的min←∞
2011-04-07 20:56阅读：
以下是选择排序的伪代码以及一些分析:
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
