排序算法(三)---直接选择排序
程序员文章站
2022-07-14 09:48:07
...
选择排序
基本思想:
从待排数列中,选取一个最小(或最大)的数,和第1位置的数交换,再从余下待排序数列中,选取最小(或最大)的一个数,和第2个位置的数交换,直到第n-1(倒数第二个)个元素和第n(末尾)个元素比较
操作方法:
时间复杂度:
第一次比较n-1次,第二次比较n-2次……最后比较1次,等差数列求和n^2/2
舍去最高项系数,O(n^2)
稳定性:
相同元素的相对位置变更,都是不稳定排序:如下
python代码示例:select_sort.py
lua代码示例:select_sort.lua
基本思想:
从待排数列中,选取一个最小(或最大)的数,和第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
上一篇: 2013年十一之静谧的明城墙遗址公园
下一篇: 2013年十一之人潮汹涌的798