十种常见的排序方法
简介
本文介绍了十种常见简单排序算法的python实现。
将要介绍的这十种排序算法分别是——冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、计数排序、基数排序、桶排序
冒泡排序
一遍遍遍历元素,两两交换其中不符合顺序的元素,将最大(或最小的)那个元素提取到最边缘的位置,直到不再有需要交换的元素为止。冒泡排序时常是排序算法中比较简单,也比较低效的一种排序方式。其时间复杂度为O(n^2)
,空间复杂度为O(1)
。
实现:1
2
3
4
5
6
7
8
9
10# 冒泡排序
def bubble_sort(data, compare=lambda x, y: x <= y):
length = len(data)
for i in range(length):
for j in range(0, length - i - 1):
if not compare(data[j], data[j + 1]):
data[j], data[j + 1] = data[j + 1], data[j]
return data
选择排序
每一次遍历元素,都选择其余元素中最小或最大的那个元素,每一次都缩小遍历范围直到遍历完成。选择排序的时间复杂度仍然为O(n^2)
,空间复杂度为O(1)
。即使如此,选择排序的性能要略优于冒泡排序。
实现1
2
3
4
5
6
7
8
9
10
11
12# 选择排序
def selection_sort(data, compare=lambda x, y: x <= y):
length = len(data)
for i in range(length):
index = i
for j in range(i + 1, length):
if not compare(data[index], data[j]):
index = j
data[index], data[i] = data[i], data[index]
return data
插入排序
插入排序的基本思想是将一个数插入一个已经排好序的序列中,并且在插入后仍然保持有序。实现上将每个序列最开始的部分视为有序,然后依次将后面的元素插入前面的有序列表。直到遍历所有元素,即得到一个全部有序的列表。插入排序的时间复杂度仍为O(n^2)
,空间复杂度为O(1)
。然而在数据量或数据基本有序时,插入排序将会拥有比冒泡和选择排序稍优异的性能。因此,经常将插入排序用作某些复合排序方法中的一部分。
实现1
2
3
4
5
6
7
8# 插入排序
def ins_sort(data, compare=lambda x, y: x <= y):
for index, value in enumerate(data):
while index > 0:
if not compare(data[index - 1], data[index]):
data[index], data[index - 1] = data[index - 1], data[index]
index -= 1
return data
希尔排序
希尔排序基于插入排序。与插入排序每次比较交换最近的元素,依次向后遍历不同,希尔排序将序列分成几组,对这几组分别进行插入排序。然后缩小分组的间隔后再次分组,执行插入排序,直到分组间隔为1。可以看出,每一次分组,序列都将越来越有序,从而执行插入排序比较、交换的次数就会越来越少。因此,希尔排序的速度要优于O(n^2),平均为O(nlog^2n),最好为O(nlogn)。
从另一个方面看,排序的实质实际上是消除序列中的逆序数。冒泡、选择、插入等一次交换仅消除一个逆序数,而希尔排序一次交换会消除多个逆序数。因此希尔排序比普通插入排序更快。
1 | # 希尔排序 |
快速排序
快速排序是分治法的体现。每次排序都选择一个基准元素,将序列分成独立的两部分,一部分中的所有元素始终小于基准元素,另一部分中的所有元素始终大于基准元素。对这两部分序列分别进行快速排序,直到序列不可再分。此时序列即是有序的。快速排序的平均时间复杂度为O(nlogn)
,最坏情况为O(n^2)
,空间复杂度为O(logn)
(递归)。
两种实现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# 快速排序1
def quick_sort1(data, begin=None, end=None, compare=lambda x, y: x <= y):
from random import randint
begin = begin if begin is not None else 0
end = end if end is not None else (len(data) - 1)
if begin >= end:
return data
key = randint(begin, end)
data[begin], data[key] = data[key], data[begin]
left = begin
for index in range(begin + 1, end + 1):
if compare(data[index], data[begin]):
left += 1
data[left], data[index] = data[index], data[left]
data[left], data[begin] = data[begin], data[left]
quick_sort1(data, begin, left - 1)
quick_sort1(data, left + 1, end)
return data
# 快速排序2
quick_sort2 = lambda data, compare=lambda x, y: x < y: \
data if len(data) < 2 else \
quick_sort2([a for a in data if compare(a, data[0])]) + \
[data[0] * data.count(data[0])] + \
quick_sort2([b for b in data if compare(data[0], b)])
归并排序
归并排序同运用了分治法的思想。归并排序将数据分为两部分,对每部分序列一次运用归并排序,直到不可再分,然后将各部分有序序列组合起来。最终返回的即为有序序列。归并排序的时间复杂度是O(nlogn)
。
实现: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
31def merge(data, i, j, k, compare):
new_data = []
data1, data2 = data[i:j + 1], data[j + 1:k + 1]
a, b = 0, 0
while a < len(data1) and b < len(data2):
if compare(data1[a], data2[b]):
new_data.append(data1[a])
a += 1
else:
new_data.append(data2[b])
b += 1
new_data.extend(data1[a:])
new_data.extend(data2[b:])
data[i:k + 1] = new_data
return data
def merge_sort(data, begin=None, end=None, compare=lambda x, y: x < y):
begin = begin if begin is not None else 0
end = end if end is not None else (len(data) - 1)
if begin < end:
mid = (begin + end) // 2
merge_sort(data, begin, mid, compare)
merge_sort(data, mid + 1, end, compare)
merge(data, begin, mid, end, compare)
return data
堆排序
参见上一篇文章
计数排序
计数排序是一种非比较的,稳定的线性时间排序算法。它将序列中的元素与一个数组中的位置对应。这个数组的下标是元素的值,这个位置储存的值是元素在新序列里所处于的位置。由n个元素组成,最大值为k的序列,首先构建一个长度为k的数组,遍历序列将它映射到数组之中,最后根据数组生成新的有序序列。因此,计数排序的时间复杂度与空间复杂度均为O(n + k)
。
计数排序适用于容易将序列的值映射为整数,且跨度不太大的情况下。并且,序列排序经常被用于更复杂的排序(如基数排序)的基本排序方法。
实现: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# 计数排序
def counting_sort(data, max_value=None):
"""
@param data: 要排序的可迭代对象
@param max: data里的最大值
"""
max_value = max_value if max_value is not None else max(data)
result = [None for _ in range(len(data))]
position = [0 for _ in range(max_value + 1)]
for value in data:
position[value] += 1
for index in range(1, max_value + 1):
position[index] += position[index - 1]
n = len(data) - 1
while n >= 0:
value = data[n]
result[position[value] - 1] = value
position[value] -= 1
n -= 1
return result
基数排序
基数排序根据给定的基数,对序列元素的每一位依次进行计数排序。因为基数排序对p位元素的每一位都执行了计数排序,因此其时间复杂度为计数排序的p倍,即O(p * (n + k))
。
与计数排序不同,只要可以将元素分成整形数字组成的几部分(如:字符串),就可以使用基数排序。
实现: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# 基数排序
def radix_sort(data, exp=10, digit=5):
from math import pow
"""
@param data: 待排序的可迭代对象
@param exp: 排序的基数
@param digit: 数据的最大位数
"""
for e in range(digit):
result = [None for _ in range(len(data))]
now_exp = pow(exp, e)
position = [0 for _ in range(exp)]
for value in data:
bit = int(value / now_exp) % exp
position[bit] += 1
for index in range(1, exp):
position[index] += position[index - 1]
n = len(data) - 1
while n >= 0:
bit = int(data[n] / now_exp) % exp
result[position[bit] - 1] = data[n]
position[bit] -= 1
n -= 1
data = result
return data
桶排序
桶排序将序列分到有限个数量的桶里,每个桶中的元素均处于某一个区间,对每个桶里的元素分别进行排序,最后再将每个桶组合起来。在序列中的值均匀分配的情况下,有n个元素,分到k个桶里,桶排序的时间复杂度为O(n + k)
,空间复杂度为O(n * k)
。
实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# 桶排序
def bucket_sort(data, bucket_size=1, compare=lambda x, y: x <= y):
min_value, max_value = int(min(data)), int(max(data))
bucket_count = (max_value - min_value) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for value in data:
buckets[(value - min_value) // bucket_size].append(value)
index = 0
for bucket in buckets:
ins_sort(bucket, compare)
for value in bucket:
data[index] = value
index += 1
return data
各个排序算法的运行时间比较
分别测试了2000个元素和20000个随机元素下,各排序算法花费的时间: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
29def compare(FAKE_COUNT=5000, FAKE_RANGE=10000):
import time
import random
fake_data = [random.randint(0, FAKE_RANGE) for _ in range(FAKE_COUNT)]
times = {}
sort_methods = [bubble_sort, selection_sort, ins_sort, shell_sort,
quick_sort1, quick_sort2, merge_sort, counting_sort,
radix_sort, bucket_sort]
for method in sort_methods:
start = time.time()
method(list(fake_data))
end = time.time()
times[method.__name__] = end - start
sorted_time = sorted(times, key=lambda x: times[x])
for key in sorted_time:
print("{key:<15}:{time:<20}".format(key=key, time=times[key]))
if __name__ == '__main__':
print('COUNT:2000\tSIZE:2000')
compare(2000, 2000)
print('COUNT:20000\tSIZE:20000')
compare(20000, 20000)
结果为:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23COUNT:2000 SIZE:2000
counting_sort :0.002000093460083008
bucket_sort :0.0020058155059814453
<lambda> :0.009976387023925781
radix_sort :0.014000892639160156
quick_sort1 :0.017019033432006836
merge_sort :0.026001930236816406
shell_sort :0.32696533203125
selection_sort :0.45195460319519043
ins_sort :0.9020371437072754
bubble_sort :1.868042230606079
COUNT:20000 SIZE:20000
counting_sort :0.01299905776977539
bucket_sort :0.025992870330810547
radix_sort :0.08400774002075195
<lambda> :0.12100505828857422
quick_sort1 :0.13498902320861816
merge_sort :0.1459970474243164
shell_sort :25.587008714675903
selection_sort :43.999064207077026
ins_sort :70.03945851325989
bubble_sort :84.87412595748901
碎碎念
诶,六月炎炎近酷暑,吹着空调写代码╮(╯_╰)╭
原文作者: Arian
原文链接: https://arianx.me/2018/06/22/Common-sort-algorithm/
许可协议: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议