FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
python-algorithm/quick_sort.py at master · lonly197/python-algorithm · GitHub
lonly197
python-algorithm
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
python-algorithm
/
quick_sort.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
103 lines (73 loc) · 3.3 KB
Breadcrumbs
python-algorithm
/
quick_sort.py
Copy path
File metadata and controls
103 lines (73 loc) · 3.3 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#!/usr/bin/env python
#coding:utf-8
"""
问题：快速排序
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
（2）快速排序的基本思想
设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
"""
#方法1
def
quickSort
(
arr
):
less
=
[]
pivotList
=
[]
more
=
[]
if
len
(
arr
)
<=
1
:
return
arr
else
:
pivot
=
arr
[
0
]
#将第一个值做为基准
for
i
in
arr
:
if
i
<
pivot
:
less
.
append
(
i
)
elif
i
>
pivot
:
more
.
append
(
i
)
else
:
pivotList
.
append
(
i
)
less
=
quickSort
(
less
)
#得到第一轮分组之后，继续将分组进行下去。
more
=
quickSort
(
more
)
return
less
+
pivotList
+
more
"""
#方法2
#将方法1写的更紧凑，彰显python特点
def qsort(L):
return (qsort([y for y in L[1:] if y < L[0]]) + L[:1] + qsort([y for y in L[1:] if y >= L[0]])) if len(L) > 1 else L
"""
"""
#方法3
#基本思想同上，只是写法上又有所变化
def qsort(list):
if not list:
return []
else:
pivot = list[0]
less = [x for x in list[1:] if x < pivot]
more = [x for x in list[1:] if x >= pivot]
return qsort(less) + [pivot] + qsort(more)
"""
#方法4
from
random
import
*
def
qSort
(
a
):
if
len
(
a
)
<=
1
:
return
a
else
:
q
=
choice
(
a
)
#基准的选择不同于前，是从数组中任意选择一个值做为基准
return
qSort
([
elem
for
elem
in
a
if
elem
<
q
])
+
[
q
]
*
a
.
count
(
q
)
+
qSort
([
elem
for
elem
in
a
if
elem
>
q
])
#方法5
#这个最狠了，一句话搞定快速排序，瞠目结舌吧。
qs
=
lambda
xs
: ( (
len
(
xs
)
<=
1
and
[
xs
])
or
[
qs
( [
x
for
x
in
xs
[
1
:]
if
x
<
xs
[
0
]] )
+
[
xs
[
0
]]
+
qs
( [
x
for
x
in
xs
[
1
:]
if
x
>=
xs
[
0
]] ) ] )[
0
]
if
__name__
==
"__main__"
:
a
=
[
4
,
65
,
2
,
-
31
,
0
,
99
,
83
,
782
,
1
]
print
quickSort
(
a
)
print
qSort
(
a
)
print
qs
(
a
)
Back
|
FazBrowse Home
|
New Git URL