排序算法(三)---直接选择排序

选择排序

基本思想：
从待排数列中，选取一个最小（或最大）的数，和[color=green]第1位置[/color]的数交换，再从余下待排序数列中，选取最小（或最大）的一个数，和[color=green]第2个位置[/color]的数交换，直到第n-1(倒数第二个)个元素和第n（末尾)个元素比较

操作方法：

9   5   6   2   1   8
---------------------
第一趟：
1   5   6   2   9   8
第二趟：
1   2   6   5   9   8
第三趟：
1   2   5   6   9   8
第四趟
1   2   5   6   9   8
第五趟
1   2   5   6   8   9

时间复杂度：
第一次比较n-1次，第二次比较n-2次……最后比较1次，等差数列求和n^2/2
舍去最高项系数，O(n^2)

稳定性：
相同元素的相对位置变更，都是不稳定排序：如下

5(第一个), 8, 5(第二个), 1
选择排序：
1  8  5(第二个)  5(第一个)

python代码示例：select_sort.py

def select_min_key(l, i):
    key = i
    for j in range(i+1, len(l)):
        if l[key] > l[j]:
        key = j
    return key

def select_sort(l):
    for i in range(0, len(l)):
        key = select_min_key(l, i) 
        if l[i] != l[key]:
            tmp = l[i]
            l[i] = l[key]
            l[key] = tmp

if __name__ == '__main__':
        l = [72,32,16,52,49,84,17,9,7,29]
        select_sort(l)
        print('result:'+str(l))

lua代码示例：select_sort.lua

function selectMinKey(t, i)
    key = i
    len = table.getn(t)
    for j = i + 1, len do
        if t[key] > t[j] then
            key = j
        end
    end
    return key
end

function select_sort(t)
    len = table.getn(t)
    for i = 1, len do
        key = selectMinKey(t, i)
        if t[i] ~= t[key] then
            tmp = t[i]
            t[i] = t[key]
            t[key] = tmp
        end
    end
end

t = {71,26,53,52,47,9,58,49,2,77}
select_sort(t)
for _,v in ipairs(t) do
   print(v)
end