考虑排序存储在数组A中的n个数：首先找出A中的最小元素并将其与A[0]中的元素进行交换。接着，找出A中的次最小元素并将其与A[1]中的元素进行交换。对A中前n-1个元素按该方式继续。该算法称为选择算法，写出代码。给出选择排序的最好情况与最坏情况运行时间。
Python代码：
def test1(numbers):
n = len(numbers)
#次数 代价
for i in range(n - 1): #n c1
minNumber = numbers[i] #n - 1 c2
minIndex = i #n - 1 c3
for j in range(i+1,n): #((n - 2)Σ(i = 0))(n - i) c4
number = numbers[j] #((n - 2)Σ(i = 0))(n - i - 1) c5
if number < minNumber: #((n - 2)Σ(i = 0))(n - i - 1) c6
minNumber = number; #最好情况：0，最坏情况：((n - 2)Σ(i = 0))(n - i - 1) c7
minIndex = j #最好情况：0，最坏情况：((n - 2)Σ(i = 0))(n - i - 1) c8
if minIndex != i: #n - 1 c9
number = numbers[i] #最好情况：0，最坏情况：n - 1 c10
numbers[i] = minNumber; #最好情况：0，最坏情况：n - 1 c11
numbers[minIndex] = number #最好情况：0，最坏情况：n - 1 c12
print numbers
输入：[4, 6, 2, 9, 1, 3, 8, 5, 7]
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]
计算可得：
1、最好情况：
c1*n + c2 * (n - 1) + c3 * (n - 1) + c4 * ((n - 2)Σ(i = 0))(n - i) + c5 * ((n - 2)Σ(i = 0))(n - i - 1) + c6 * ((n - 2)Σ(i = 0))(n - i - 1) + c7 * 0 + c8 * 0 + c9 * (n - 1) + c10 * 0 + c11 * 0 + c12 * 0 = an^2 + bn + c
(其中a、b、c是依赖于代价c的常量)
2、最坏情况：
c1*n + c2 * (n - 1) + c3 * (n - 1) + c4 * ((n - 2)Σ(i = 0))(n - i) + c5 * ((n - 2)Σ(i = 0))(n - i - 1) + c6 * ((n - 2)Σ(i = 0))(n - i - 1) + c7 * ((n - 2)Σ(i = 0))(n - i - 1) + c8 * ((n - 2)Σ(i = 0))(n - i - 1) + c9 * (n - 1) + c10 * (n - 1) + c11 * (n - 1) + c12 * (n - 1) = an^2 + bn + c
(其中a、b、c是依赖于代价c的常量)
由此可知，最好情况和最坏情况的运行时间都可表示为θn^2。
