十一.Python排序: 冒泡排序、直接排序、简单选择排序

1.冒泡排序

冒泡排序是一种交换排序。

什么是交换排序呢?

交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。

代码示例:

def bubble_sort(demo:list):
length = len(demo)
for i in range(length):
print("*"*30)
for j  in range(length-i-1):
if demo[j] > demo[j+1]:
demo[j],demo[j+1] = demo[j+1], demo[j]
print('{}次:'.format(i),demo)
print("最终排序:",demo)
if __name__ == '__main__':
num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
bubble_sort(num_list)

结果:

******************************
0次: [4, 15, 2, 33, 57, 9, 52, 72, 55, 90]
******************************
1次: [4, 2, 15, 33, 9, 52, 57, 55, 72, 90]
******************************
2次: [2, 4, 15, 9, 33, 52, 55, 57, 72, 90]
******************************
3次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
4次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
5次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
6次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
7次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
8次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
******************************
9次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
最终排序: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]

从结果中看出,其实在第3次时,就已经完成了排序,之后的迭代只是在浪费时间,所以可以优化下。

代码示例:

def bubble_sort(demo:list):
flag = False
length = len(demo)
for i in range(length):
print("*"*30)
for j  in range(length-i-1):
flag = False
if demo[j] > demo[j+1]:
demo[j],demo[j+1] = demo[j+1], demo[j]
flag = True
print('{}次:'.format(i), demo)
if not flag:
break
print("最终排序:",demo)
if __name__ == '__main__':
num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
bubble_sort(num_list)

结果

******************************
1次: [4, 2, 15, 33, 9, 52, 57, 55, 72, 90]
******************************
2次: [2, 4, 15, 9, 33, 52, 55, 57, 72, 90]
******************************
3次: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
最终排序: [2, 4, 9, 15, 33, 52, 55, 57, 72, 90]

2.直接排序

原理:

在未排序序列中,构建一个子排序序列,直至全部数据排序完成。

将待排序的数,插入到已经排序的序列中合适的位置。

增加一个哨兵,放入待比较值,让它和后面已经排序好的序列比较,找到合适的插入点。

代码示例

def direct_insert_sort(demo):
print('排序前{}'.format(demo))
demo = [0] + demo
length = len(demo)
for i in range(2, length):
demo[0] = demo[i]  # 放置哨兵
j = i - 1
if demo[j] > demo[0]:
while demo[j] > demo[0]:
demo[j+1] = demo[j]
j -= 1
demo[j + 1] = demo[0]
print('{}次:{}'.format(i, demo))
demo = demo[1:]
print("最终排序{}".format(demo))
if __name__ == '__main__':
num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
direct_insert_sort(num_list)

结果:

排序前[33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
2次:[4, 4, 33, 15, 2, 72, 57, 9, 52, 90, 55]
3次:[15, 4, 15, 33, 2, 72, 57, 9, 52, 90, 55]
4次:[2, 2, 4, 15, 33, 72, 57, 9, 52, 90, 55]
5次:[72, 2, 4, 15, 33, 72, 57, 9, 52, 90, 55]
6次:[57, 2, 4, 15, 33, 57, 72, 9, 52, 90, 55]
7次:[9, 2, 4, 9, 15, 33, 57, 72, 52, 90, 55]
8次:[52, 2, 4, 9, 15, 33, 52, 57, 72, 90, 55]
9次:[90, 2, 4, 9, 15, 33, 52, 57, 72, 90, 55]
10次:[55, 2, 4, 9, 15, 33, 52, 55, 57, 72, 90]
最终排序[2, 4, 9, 15, 33, 52, 55, 57, 72, 90]

3.简单选择排序

简单选择排序是一种选择排序。

选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

代码示例

def simple_select_sort1(demo:list):
"""
简单选择排序
:param demo:
:return:
"""
length = len(demo)
for i in range(length):
maxindex = i
for j in range(i + 1, length):
if demo[maxindex] < demo[j]:
maxindex = j
if i != maxindex:
demo[i], demo[maxindex] = demo[maxindex], demo[i]
print("{}次{}".format(i, demo))
print("最终排序".format(demo))
def simple_select_sort2(demo:list):
"""
优化后简单选择排序
:param demo:
:return:
"""
length = len(demo)
for i in range(length // 2):
maxindex = i
minindex = -i - 1
minorgin = minindex
for j in range(i + 1, length - i):
if demo[maxindex] < demo[j]:
maxindex = j
if demo[minindex] > demo[-j - 1]:
minindex = -j - 1
if i != maxindex:
demo[i], demo[maxindex] = demo[maxindex], demo[i]
if i == length + minindex:
minindex = maxindex
if minorgin != minindex:
demo[minorgin], demo[minindex] = demo[minindex], demo[minorgin]
print("{}次{}".format(i, demo))
print("最终排序{}".format(demo))
if __name__ == '__main__':
num_list = [33, 4, 15, 2, 72, 57, 9, 52, 90, 55]
simple_select_sort1(num_list)
print("*" * 40)
simple_select_sort2(num_list)

结果

0次[90, 4, 15, 2, 72, 57, 9, 52, 33, 55]
1次[90, 72, 15, 2, 4, 57, 9, 52, 33, 55]
2次[90, 72, 57, 2, 4, 15, 9, 52, 33, 55]
3次[90, 72, 57, 55, 4, 15, 9, 52, 33, 2]
4次[90, 72, 57, 55, 52, 15, 9, 4, 33, 2]
5次[90, 72, 57, 55, 52, 33, 9, 4, 15, 2]
6次[90, 72, 57, 55, 52, 33, 15, 4, 9, 2]
7次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
8次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
9次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
最终排序
****************************************
0次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
1次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
2次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
3次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
4次[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
最终排序[90, 72, 57, 55, 52, 33, 15, 9, 4, 2]
SegmentFault博客
我还没有学会写个人说明!
上一篇

达摩院2021年十大科技趋势出炉:量子计算、脑机接口、第三代半导体应用……

下一篇

美国一男子用喷火器清除门前积雪引围观

你也可能喜欢

评论已经被关闭。

插入图片