选择算法

考虑排序存储在数组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。