选择算法  伪代码:

 for j=1 to n-1
   smallest = j
   for i=j+1 to n
     if  A[i]<A[smallest]
         smallest=i
   A[j]=A[smallest]
   
循环不变式
在for循环(循环变量为j)的每次 迭×××始,包含元素A[1..j-1]对的子数组都是排好序的(由数组[1..n]的j-1个最小元素组成)

循环终止的条件是就j>n-1,因为每次循环的迭代j增加1,所以必有j=n。将j=n带入循环不变式的表示中,有子数组A[1..n-1]中的元素都是排好序的(由数组A[1..n]的n-1个最小元素组成),因此A[n]是其中最大的元素。所以整个数组都已拍好序。


最好运行情况与最坏运行情况都是  (n^2)