数据结构面试中经常会被问到篇排序相关的问题,那么这篇文章会研究下怎么用python来实现排序。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
#coding:utf-8

# 冒泡排序
def maopao():
a = [2,1,4,3,9,5,6,8,7]
for i in range(len(a)-1):
for j in range(len(a)-1-i):
if a[j]>a[j+1]:
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
print(a)
maopao()

结果为:

1
[1, 2, 3, 4, 5, 6, 7, 8, 9]


归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 归并排序
def merge(a,b):
i,j = 0,0
c = []
while i<=len(a)-1 and j<=len(b)-1:
if a[i]<b[j]:
c.append(a[i])
i+=1
else:
c.append(b[j])
j+=1
if i<=len(a)-1:
for m in a[i:]:
c.append(m)

if j<=len(b)-1:
for n in b[j:]:
c.append(n)
return c

def guibing(a):
if len(a)<=1:
return a
center = int(len(a)/2)
left = guibing(a[:center])
right = guibing(a[center:])
return merge(left,right)

print(guibing([2,1,4,3,9,5,6,8,7]))

结果为:

1
[1, 2, 3, 4, 5, 6, 7, 8, 9]


 快速排序

快速排序Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 快速排序    
def kpsort(left,right,a):
based = a[left]
i = left
j = right
while i < j:
# 从数组右边开始遍历
while a[j]>=based and i<j:
j -= 1
a[i] = a[j]
while a[i]<=based and i<j:
i += 1

a[j]= a[i]
a[i] = based

return i

def kuaipai(left,right,a):
if left<right:
p = kpsort(left,right,a)
kuaipai(left,p-1,a)
kuaipai(p+1,right,a)

return a

print(kuaipai(0,8,a =[2,1,4,3,9,5,6,8,7]))

结果为

1
[1, 2, 3, 4, 5, 6, 7, 8, 9]


打开微信扫一扫,关注微信公众号【搜索与推荐Wiki】