个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
28
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Python八大常见排序算法定义、实现及时间消耗效率分析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
本文实例讲述了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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：八大排序算法
'''
import
time
import
random
time_dict
=
{}
def
time_deco(sort_func):
'''''
时间计算的装饰器函数,可用于计算函数执行时间
'''
def
wrapper(num_list):
start_time
=
time.time()
res
=
sort_func(num_list)
end_time
=
time.time()
time_dict[
str
(sort_func)]
=
(end_time
-
start_time)
*
1000
print
'耗时为：'
,(end_time
-
start_time)
*
1000
print
'结果为：'
, res
return
wrapper
def
random_nums_generator(max_value
=
1000
, total_nums
=
20
):
'''''
随机数列表生成器
一些常用函数：
random随机数生成
random.random()用于生成一个0到1之间的随机数:0 <= n < 1.0；
random.uniform(a, b)，用于生成一个指定范围内的随机符点数，两个参数其中一个是上限，一个是下限。min(a,b) <= n <= max(a,b)；
randdom.randint(a, b), 用于生成一个指定范围内的整数，其中a是下限，b是上限： a<= n <= b；
random.randrange(start, stop, step), 从指定范围内，按指定基数递增的集合获取一个随机数；
random.choice(sequence), 从序列中获取一个随机元素；
random.shuffle(x), 用于将一个列表中的元素打乱；
random.sample(sequence, k), 从指定序列中随机获取指定长度的片断；
'''
num_list
=
[]
for
i
in
range
(total_nums):
num_list.append(random.randint(
0
,max_value))
return
num_list
#@time_deco
def
Bubble_sort(num_list):
'''''
冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
'''
for
i
in
range
(
len
(num_list)):
for
j
in
range
(i,
len
(num_list)):
if
num_list[i]>num_list[j]:
#这里是升序排序
num_list[i], num_list[j]
=
num_list[j], num_list[i]
return
num_list
#@time_deco
def
Insert_sort(num_list):
'''''
直接插入排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
'''
for
i
in
range
(
len
(num_list)):
for
j
in
range
(
0
,i):
if
num_list[i]<num_list[j]:
#这里是升序排序,跟冒泡排序差别在于，冒泡是向后遍历，这个是向前遍历
num_list[i], num_list[j]
=
num_list[j], num_list[i]
return
num_list
#@time_deco
def
Select_sort(num_list):
'''''
选择排序，时间复杂度O(n^2)，空间复杂度O(1)，不是稳定排序
'''
for
i
in
range
(
len
(num_list)):
min_value_index
=
i
for
j
in
range
(i,
len
(num_list)):
if
num_list[j]<num_list[min_value_index]:
min_value_index
=
j
#乍一看，感觉冒泡，选择，插入都很像，选择跟冒泡的区别在于：冒泡是发现大
#小数目顺序不对就交换，而选择排序是一轮遍历结束后选出最小值才交换，效率更高
num_list[i], num_list[min_value_index]
=
num_list[min_value_index], num_list[i]
return
num_list
#@time_deco
def
Merge_sort(num_list):
'''''
归并排序，时间复杂度O(nlog₂n)，空间复杂度：O(1)，是稳定排序
'''
if
len
(num_list)
=
=
1
:
return
num_list
length
=
len
(num_list)
/
2
list1
=
num_list[:length]
list2
=
num_list[length:]
result_list
=
[]
while
len
(list1)
and
len
(list2):
if
list1[
0
]<
=
list2[
0
]:
result_list.append(list1[
0
])
del
list1[
0
]
#这里需要删除列表中已经被加入到加过列表中的元素，否则最后比较完后列表
else
:
#中剩余元素无法添加
result_list.append(list2[
0
])
del
list1[
0
]
if
len
(list1):
#遍历比较完毕后列表中剩余元素的添加
result_list
+
=
list1
else
:
result_list
+
=
list2
return
result_list
#@time_deco
def
Shell_sort(num_list):
'''''
希尔排序，时间复杂度：O(n)，空间复杂度：O(n^2),不是稳定排序算法
'''
new_list
=
[]
for
one_num
in
num_list:
new_list.append(one_num)
count
=
len
(new_list)
step
=
count
/
2
;
while
step>
0
:
i
=
0
while
i<count:
j
=
i
+
step
while
j<count:
t
=
new_list.pop(j)
k
=
j
-
step
while
k>
=
0
:
if
t>
=
new_list[k]:
new_list.insert(k
+
1
, t)
break
k
=
k
-
step
if
k<
0
:
new_list.insert(
0
, t)
#print '---------本轮结果为：--------'
#print new_list
j
=
j
+
step
#print j
i
=
i
+
1
#print i
step
=
step
/
2
#希尔排序是一个更新步长的算法
return
new_list
#@time_deco
def
Tong_sort(num_list):
'''''
桶排序，时间复杂度O(1)，空间复杂度与最大数字有关，可以认为是O(n)，典型的空间换时间的做法
'''
original_list
=
[]
total_num
=
max
(num_list)
#获取桶的个数
for
i
in
range
(total_num
+
1
):
#要注意这里需要的数组元素个数总数比total_num数多一个因为下标从0开始
original_list.append(
0
)
for
num
in
num_list:
original_list[num]
+
=
1
result_list
=
[]
for
j
in
range
(
len
(original_list)):
if
original_list[j] !
=
0
:
for
h
in
range
(
0
,original_list[j]):
result_list.append(j)
return
result_list
def
Quick_sort(num_list):
'''''
快速排序，时间复杂度：O(nlog₂n)，空间复杂度：O(nlog₂n)，不是稳定排序
'''
if
len
(num_list)<
2
:
return
num_list
left_list
=
[]
#存放比基准结点小的元素
right_list
=
[]
#存放比基准元素大的元素
base_node
=
num_list.pop(
0
)
#在这里采用pop()方法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量
#在这里不能使用del()方法，因为删除之后无法再赋值给其他变量使用，导致最终数据缺失
#快排每轮可以确定一个元素的位置，之后递归地对两边的元素进行排序
for
one_num
in
num_list:
if
one_num < base_node:
left_list.append(one_num)
else
:
right_list.append(one_num)
return
Quick_sort(left_list)
+
[base_node]
+
Quick_sort(right_list)
def
Heap_adjust(num_list, i, size):
left_child
=
2
*
i
+
1
right_child
=
2
*
i
+
2
max_temp
=
i
#print left_child, right_child, max_temp
if
left_child<size
and
num_list[left_child]>num_list[max_temp]:
max_temp
=
left_child
if
right_child<size
and
num_list[right_child]>num_list[max_temp]:
max_temp
=
right_child
if
max_temp !
=
i:
num_list[i], num_list[max_temp]
=
num_list[max_temp], num_list[i]
Heap_adjust(num_list, max_temp, size)
#避免调整之后以max为父节点的子树不是堆
def
Create_heap(num_list, size):
a
=
size
/
2
-
1
for
i
in
range
(a,
-
1
,
-
1
):
#print '**********', i
Heap_adjust(num_list, i, size)
#@time_deco
def
Heap_sort(num_list):
'''''
堆排序，时间复杂度：O(nlog₂n)，空间复杂度：O(1)，不是稳定排序
'''
size
=
len
(num_list)
Create_heap(num_list, size)
i
=
size
-
1
while
i >
0
:
num_list[
0
], num_list[i]
=
num_list[i], num_list[
0
]
size
-
=
1
i
-
=
1
Heap_adjust(num_list,
0
, size)
return
num_list
if
__name__
=
=
'__main__'
:
num_list
=
random_nums_generator(max_value
=
100
, total_nums
=
50
)
print
'Bubble_sort'
, Bubble_sort(num_list)
print
'Insert_sort'
, Insert_sort(num_list)
print
'Select_sort'
, Select_sort(num_list)
print
'Merge_sort'
, Merge_sort(num_list)
print
'Shell_sort'
, Shell_sort(num_list)
print
'Tong_sort'
, Tong_sort(num_list)
print
'Heap_sort'
, Heap_sort(num_list)
print
'Quick_sort'
, Quick_sort(num_list)
# print '-----------------------------------------------------------------------------'
# for k,v in time_dict.items():
# print k, v
|
结果如下:
Bubble_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Insert_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Select_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Merge_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Shell_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Tong_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Heap_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] Quick_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998] 。
这里没有使用到装饰器，主要自己对这个装饰器不太了解，在快速排序的时候报错了，也没有去解决，这里简单贴一下一个测试样例使用装饰器的结果吧:
Bubble_sort 耗时为： 0.0290870666504 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Insert_sort 耗时为： 0.0209808349609 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Select_sort 耗时为： 0.0259876251221 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Merge_sort 耗时为： 0.0138282775879 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Shell_sort 耗时为： 0.113964080811 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Tong_sort 耗时为： 0.0460147857666 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Heap_sort 耗时为： 0.046968460083 结果为： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] None Quick_sort [5, 45, 46, 63, 81, 83, 89, 89, 89, 90] ----------------------------------------------------------------------------- <function Shell_sort at 0x7f8ab9d34410> 0.113964080811 <function Select_sort at 0x7f8ab9d34230> 0.0259876251221 <function Insert_sort at 0x7f8ab9d34140> 0.0209808349609 <function Heap_sort at 0x7f8ab9d34758> 0.046968460083 <function Merge_sort at 0x7f8ab9d34320> 0.0138282775879 <function Tong_sort at 0x7f8ab9d34500> 0.0460147857666 <function Bubble_sort at 0x7f8ab9d34050> 0.0290870666504 。
接下来有时间的话我想学一下装饰器的东西，感觉对于模式化的东西装饰器简直就是一个神器，但是得明白会用会写才行哈！ 。
希望本文所述对大家Python程序设计有所帮助.
原文链接：https://blog.csdn.net/together_cz/article/details/76049122 。
最后此篇关于Python八大常见排序算法定义、实现及时间消耗效率分析的文章就讲到这里了,如果你想了解更多关于Python八大常见排序算法定义、实现及时间消耗效率分析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
28
4
0
背景: 我最近一直在使用 JPA，我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。 我们公司使用大量非 SQL 数据库，特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
我已经在我的 maven pom 中添加了这些构建配置，因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。 允许在行(实体)中进行迭代，并在对当前
好像没有，因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情，要么这不应该发
在 C# 中，如果 A 实现 IX 并且 B 继承自 A ，是否必然遵循 B 实现 IX？如果是，是因为 LSP 吗？之间有什么区别吗: 1. Interface IX; Class A : IX;
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0
我将把国际象棋游戏表示为 C++ 结构。我认为，最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。 这是一个好的方法吗？ struct TreeElement{ SomeMoveType
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名，然后检查用户名是否已被占用。如果采用该方法，则该方法应该返回带有数据库中未采用的数字的用户名。 例子: “贾
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象，并且我有一个二维数组来保存两个给定顶点
我目前正在 ika 中开发我的 Python 游戏，它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而，我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏，但我想供应 4-
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。 它必须能够将信息发布到 DHT 并检索它。 最佳答案 OpenDHT是
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时，它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!？ 最佳答案 “C++ 实现”是指编译器加上链接
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印
在很多情况下，我需要在 C# 中访问合适的哈希算法，从重写 GetHashCode 到对数据执行快速比较/查找。 我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是，我从未见过 C# 实现的
目录 LRU缓存替换策略 核心思想 不适用场景 算法基本实现 算法优化
1. 绪论 在前面文章中提到 空间直角坐标系相互转换 ，测绘坐标转换时，一般涉及到的情况是：两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中，WGS-84坐标系、54北京坐标系
在软件开发过程中，有时候我们需要定时地检查数据库中的数据，并在发现新增数据时触发一个动作。为了实现这个需求，我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .
二分查找 二分查找算法，说白了就是在有序的数组里面给予一个存在数组里面的值key，然后将其先和数组中间的比较，如果key大于中间值，进行下一次mid后面的比较，直到找到相等的，就可以得到它的位置。
我是一名优秀的程序员,十分优秀！