Python的几种常见排序

101 阅读 0 评论 67 点赞

我是靠谱客的博主玩命曲奇，这篇文章主要介绍Python的几种常见排序，现在分享给大家，希望可以做个参考。

常见的排序有：快速排序、冒泡排序、希尔排序、选择排序、插入排序、归并排序

冒泡排序：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def bubble_sort(li):
n = len(li)
# 遍历列表，让下标从0取得列表右边倒数对二个位置
# 一趟冒泡，让最大的数移动到最右边
for j in range(n-1):
flag = 0
for i in range(n-1-j):
# 拿当前位置的数与下一个数进行比较
if li[i] > li[i+1]:
li[i],li[i+1] = li[i+1],li[i]
flag += 1
# 内层循环如果循环一次后，flag没有变化的话，说明列表已经是有序的
if flag == 0:
break
if __name__ = '__main__':
l = [1,4,6,8,5]
bubble(l)
print(l)

插入排序：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def insert_sort(li):
n = len(li)
# 认为第一个数是有序的，从后面取一个数，倒着往前遍历，插入到前面的有序队列中
for j in range(1, n):
for i in range(j, 0, -1):
if li[i] <li[i-1]:
li[i],li[i-1] = li[i-1],li[i]
else:
break
if __name__ = '__main__':
l = [1,3,7,9,4,3]
insert_sort(l)
print(l)

选择排序：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
def select_sort(li):
n = len(li)
# 记录0位置的数据，认为0位置的数据最小
temp = 0
# 依次跟后面的数据进行比较
for i in range(1, n):
if li[i] < li[temp]:
# 把最小数的位置记起来
temp = i
# 循环结束时，temp指向的是最小数的位置
li[temp],li[0] = li[0],li[temp]

希尔排序：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shell_sort(li):
n = len(li)
# 定义步长
gap = n//2
# 让步长由大变小，最后变为1
while gap >= 1:
# 按照步长，把数据分成两半，遍历后一半数据
for i in range(gap, n):
# 让当前位置跟减去一个步长的下标数进行比较
while (i - gap) >= 0:
if li[i]<li[i-gap]:
li[i],li[i-gap] = li[i-gap], li[i]
i -= gap
gap //= 2

快速排序：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quink_sort(li, start, end):
# 定义两个变量记录下标位置
low = start
high = end
#　定义一个用来比较的数字
mind = li[low]
while low < high:
while low < high and li[high] >= mind:
high -= 1
li[low] = li[high]
while low < high and li[low] < mind:
low += 1
li[high] = li[low]
li[low] = mind
quink_sort(li, start, low-1)
quink_sort(li, low+1, end)