`

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

阅读更多
选择排序

基本思想:
  从待排数列中,选取一个最小(或最大)的数,和第1位置的数交换,再从余下待排序数列中,选取最小(或最大)的一个数,和第2个位置的数交换,直到第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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics