前言
由于最近开始深入学习 python 数据结构，简单的用python来实现一波十大经典排序算法。分别是：
冒泡排序选择排序插入排序希尔排序归并排序快速排序堆排序计数排序桶排序基数排序
冒泡排序
基本原理
比较类排序算法。算法描述如下(假设是升序排序)：
比较相邻的元素，如果第一个元素比第二个大，就交换它们；对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后已经选出的有序元素；持续对剩下的无序元素重复上面的步骤，直到排序完成。
算法时间复杂度
O(
n
2
n^2
n2)
算法实现
'''冒泡排序'''
def BubbleSort(array
):
length
= len(array
)
for i
in range(length
):
for j
in range(length
-i
-1):
if array
[j
] > array
[j
+1]: array
[j
+1], array
[j
] = array
[j
], array
[j
+1]
return array
选择排序
基本原理
比较类排序算法。算法描述如下(假设是升序排序)：
首先在未排序序列中找到最小元素，存放到排序序列的起始位置；再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾；重复第二步，直到所有元素均排序完毕。
算法时间复杂度
O(
n
2
n^2
n2)
算法实现
'''选择排序'''
def SelectionSort(array
):
length
= len(array
)
for i
in range(length
-1):
idx_min
= i
for j
in range(i
+1, length
):
if array
[j
] < array
[idx_min
]:
idx_min
= j
array
[i
], array
[idx_min
] = array
[idx_min
], array
[i
]
return array
插入排序
基本原理
比较类排序算法。算法描述如下(假设是升序排序)：
从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素(已排序)大于新元素，将该元素移到下一位置；重复第三步，直到找到已排序的元素小于或等于新元素的位置；将新元素插入到该位置；重复第二到第五步，直到排序完成。
算法时间复杂度
O(
n
2
n^2
n2)
算法实现
'''插入排序'''
def InsertionSort(array
):
length
= len(array
)
for i
in range(1, length
):
pointer
, cur
= i
- 1, array
[i
]
while pointer
>= 0 and array
[pointer
] > cur
:
array
[pointer
+1] = array
[pointer
]
pointer
-= 1
array
[pointer
+1] = cur
return array
希尔排序
基本原理
比较类排序算法。其基本思想是把数据按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的数越来越多，当增量减至1时，整个文件恰被分成一组，算法终止。算法描述如下(假设是升序排序)：
选择一个增量序列 t1, t2, … tk = 1；按增量序列个数k，对序列进行k次排序；每次排序，根据对应的增量 ，将待排序列分割成若干长度为m的子序列，分别对各子序列进行直接插入排序。
算法时间复杂度
O(
n
1.3
n^{1.3}
n1.3)
算法实现
'''希尔排序'''
def ShellSort(array
):
length
= len(array
)
gap
= length
// 2
while gap
> 0:
for i
in range(gap
, length
):
j
, cur
= i
, array
[i
]
while (j
- gap
>= 0) and (cur
< array
[j
- gap
]):
array
[j
] = array
[j
- gap
]
j
= j
- gap
array
[j
] = cur
gap
= gap
// 2
return array
归并排序
基本原理
比较类排序算法。该算法采用了分治法的思想，将已有序的子序列合并，得到完全有序的序列。算法描述如下(假设是升序排序)：
把长度为n的输入序列分为两个长度为 的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。
算法时间复杂度
O(
n
l
o
g
2
n
nlog_2n
nlog2n)
算法实现
'''数组合并'''
def Merge(array_1
, array_2
):
result
= []
while array_1
and array_2
:
if array_1
[0] < array_2
[0]:
result
.append
(array_1
.pop
(0))
else:
result
.append
(array_2
.pop
(0))
if array_1
:
result
+= array_1
if array_2
:
result
+= array_2
return result
'''归并排序'''
def MergeSort(array
):
if len(array
) < 2: return array
pointer
= len(array
) // 2
left
= array
[:pointer
]
right
= array
[pointer
:]
return Merge
(MergeSort
(left
), MergeSort
(right
))
快速排序
基本原理
比较类排序算法。基本思想是通过一次排序将待排序数据分隔成独立的两部分，其中一部分数据均比另一部分的数据小。然后分别对这两部分数据继续进行排序，直到整个序列有序。算法描述如下(假设是升序排序)：
从数列中挑出一个元素，称为“基准”；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准的后面(相同的数可以到任一边)；分别对步骤二中的两个子序列再使用快速排序；重复上述步骤，直到排序完成。
算法时间复杂度
O(
n
l
o
g
2
n
nlog_2n
nlog2n)
算法实现
'''快速排序'''
def QuickSort(array
, left
, right
):
if left
>= right
:
return array
pivot
, i
, j
= array
[left
], left
, right
while i
< j
:
while i
< j
and array
[j
] >= pivot
:
j
-= 1
array
[i
] = array
[j
]
while i
< j
and array
[i
] <= pivot
:
i
+= 1
array
[j
] = array
[i
]
array
[j
] = pivot
QuickSort
(array
, left
, i
-1)
QuickSort
(array
, left
+1, right
)
return array
堆排序
基本原理
比较类排序算法。算法描述如下(假设是升序排序)：
将初始待排序序列 R1, R2, … ,Rn 构建成大顶堆，此堆为初始的无序区；将堆顶元素 R[1] 和最后一个元素 R[n] 交换，此时得到新的无序区 R1, R2, … ,R(n-1) 和新的有序区 Rn ，且满足：R[1, 2, … , n-1] <= R[n] ；由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要将当前无序区 R1, R2, … ,R(n-1) 调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区 R1, R2, … ,R(n-2) 和新的有序区 R(n-1), Rn 。不断重复此过程直到有序区的元素个数为 n-1 ，则整个排序过程完成。
算法时间复杂度
O(
n
l
o
g
2
n
nlog_2n
nlog2n)
算法实现
'''堆化'''
def heapify(array
, length
, i
):
largest
= i
left
= 2 * i
+ 1
right
= 2 * i
+ 2
if left
< length
and array
[largest
] < array
[left
]:
largest
= left
if right
< length
and array
[largest
] < array
[right
]:
largest
= right
if largest
!= i
:
array
[i
], array
[largest
] = array
[largest
], array
[i
]
heapify
(array
, length
, largest
)
'''堆排序'''
def HeapSort(array
):
length
= len(array
)
for i
in range(length
, -1, -1):
heapify
(array
, length
, i
)
for i
in range(length
-1, 0, -1):
array
[i
], array
[0] = array
[0], array
[i
]
heapify
(array
, i
, 0)
return array
计数排序
基本原理
非比较类排序算法。算法描述如下(假设是升序排序)：
找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)；反向填充目标数组，将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。
算法时间复杂度
O(
n
+
k
n+k
n+k)
算法实现
'''计数排序(假设都是0/正整数)'''
def CountingSort(array
):
length
= len(array
)
max_value
= max(array
)
count
= [0 for _
in range(max_value
+1)]
output
= [0 for _
in range(length
)]
for i
in range(length
):
count
[array
[i
]] += 1
for i
in range(1, len(count
)):
count
[i
] += count
[i
-1]
for i
in range(length
):
output
[count
[array
[i
]]-1] = array
[i
]
count
[array
[i
]] -= 1
return output
桶排序
基本原理
非比较类排序算法。算法描述如下(假设是升序排序)：
设置一个定量的数组当作空桶集合；遍历输入数据，并且把数据一个个放到对应的桶里去(即在每个空桶放一定数值范围的数据)；对每个非空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。
算法时间复杂度
O(
n
+
k
n+k
n+k)
算法实现
'''桶排序(假设都是整数)'''
def BucketSort(array
):
max_value
, min_value
, length
= max(array
), min(array
), len(array
)
buckets
= [0 for _
in range(min_value
, max_value
+1)]
for i
in range(length
):
buckets
[array
[i
]-min_value
] += 1
output
= []
for i
in range(len(buckets
)):
if buckets
[i
] != 0:
output
+= [i
+min_value
] * buckets
[i
]
return output
基数排序
基本原理
非比较类排序算法。其实就是先按最低位排序，然后按照高位排序，直到最高位。算法描述如下(假设是升序排序)：
取得数组中的最大数，并取得其位数； arr为原始数组，从最低位开始取每个位组成的基数数组；对基数进行计数排序(利用计数排序适用于小范围数的特点)。
算法时间复杂度
O(
n
∗
k
n*k
n∗k)
算法实现
'''基数排序(假设都是整数)'''
def RadixSort(array
):
max_value
= max(array
)
num_digits
= len(str(max_value
))
for i
in range(num_digits
):
buckets
= [[] for k
in range(10)]
for j
in array
:
buckets
[int(j
/ (10 ** i
)) % 10].append
(j
)
output
= [m
for bucket
in buckets
for m
in bucket
]
return output
功能介绍完毕🤞
最后还是希望你们能给我点一波小小的关注。
奉上自己诚挚的爱心💖
