选择排序

假设我们有这样的一个数组 [10, 2, 5, 3, 6, 4]. 在选择排序算法时, 会进行如下操作

1. 10 与 2, 5, 3, 6, 4进行比较, 找到最小的值放到左边. 因此第一轮排序之后结果为 [2, 10, 5, 3, 6, 4]
2. 10 与 5, 3, 6, 4进行比较, 找到最小的值放到左边. 因此第二轮排序之后结果为 [2, 3, 5, 10, 6, 4]
3. 5 与 10, 6, 4进行比较, 找到最小的值放到左边. 因此第二轮排序之后结果为 [2, 3, 4, 10, 6, 5]
4. …以此类推

我们看一下选择排序的实现

#-*- coding=utf-8 -*-

data = [5, 4, 3, 2, 1]
print data

def sort():
    for i in range(0, len(data)):
        min  = i
        for j in range(i, len(data)):
            if data[j] < data[min]:
                min = j

        tmp = data[i]
        data[i] = data[min]
        data[min] = tmp
        print str(data[i]) + " compore " + str(data[j]) + " -> " + str(data)

sort()

结果为

[5, 4, 3, 2, 1]
1 compore 5 -> [1, 4, 3, 2, 5]
2 compore 5 -> [1, 2, 3, 4, 5]
3 compore 5 -> [1, 2, 3, 4, 5]
4 compore 5 -> [1, 2, 3, 4, 5]
5 compore 5 -> [1, 2, 3, 4, 5]

选择排序的运行时间和输入没有关系. 因为在排序的过程中, 每一个位置的数字都会跟后边的数字比较一遍.所以哪怕数组是排序好的, 仍然会进行比较.

那么选择排序会比较多少次呢? 答案是(N + (N - 1) + (N - 2) ... 1) = N^2/2.

相关网站

• visualgo
• Sorting Algorithm