1.排序算法（学习自用）
1.冒泡排序算法步调
相邻的元素之间对比，每次早出最大值或最小值放到最后或前面，所以形象的称为冒泡。
特点
n个数排序则举行n轮，每轮比力n-i次。所以时间复杂度为O(n^2)，空间复杂度为O(1)，该排序算法稳固。
代码模板
n = int(input())
a = list(map(int, input().split()))
for i in range(1, n-1):
for j in range(0, n - i):
if a > a:
a, a = a, a
print(' '.join(map(str, a)))
2.选择排序
算法步调
从左往右找到最小元素，放在起始位置。依次找到第i个位置的元素。
特点
n个数排序有n个位置，每轮比力n-i次。所以时间复杂度为O(n^2)，空间复杂度为O(1)，该排序算法稳固。
代码模板
n = int(input())
a = list(map(int, input().split()))
for i in range(0, n-1):
min_val = a
min_id = i
for j in range(i, n):
if a < min_val:
min_val = a
min_id = j
a, a = a, a
print(' '.join(map(str, a)))
3.插入排序
算法步调
第一个元素看做已排序，从左往右遍历每一个元素。在已排序元素中从后往前扫描：假如当前元素大于新元素，则钙元素移动到后一位。
简朴来说，对第i个元素从i向左到i-1找合适的位置插入。
特点
n个数排序则举行n轮插入，每轮比力i次。所以时间复杂度为O(n^2)，空间复杂度为O(1)，该排序算法不稳固。
代码模板
n = int(input())
a = list(map(int, input().split()))
for i in range(1, n):
value = a
insert_id = 0
for j in range(i - 1, -1, -1):
if a > value:
a = a
else:
insert_id = j + 1
break
a = value
print(' '.join(map(str, a)))
4.快速排序
算法步调
找一个基准值x，把列表分为三部分：小于等于x的数、x、大于x的数字。左部分和右部分递归使用该计谋。
特点
时间复杂度为O(n log(n))，空间复杂度为O(n log(n))，该排序算法不稳固。
代码模板
def partition(a, left, right):
id = left + 1
for i in range(left + 1, right + 1):
if a <= a:
a, a = a, a
id += 1
a, a = a, a
return id - 1
def quicksort(a, left, right):
if left < right:
mid = partition(a, left, right)
quicksort(a, left, mid - 1)
quicksort(a, mid + 1, right)
n = int(input())
a = list(map(int, input().split()))
quicksort(a, 0 , n - 1)
print(' '.join(map(str, a)))
5.归并排序
算法步调
先把数组分成两部分，每部分递归处置惩罚酿成有序，将两个有序列表合并起来。
代码模板
n = int(input())
a = list(map(int, input().split()))
def merge(A,B):
result = []
while len(A)!=0 and len(B)!=0:
if A <= B:
result.append(A.pop(0))
else:
result.append(B.pop(0))
result.extend(A)
result.extend(B)
return result
def mergesort(A):
if len(A)<2:
return A
mid = len(A)//2
left =mergesort(A[:mid])
right = mergesort(A)
return merge(left, right)
print(' '.join(map(str, mergesort(a))))
6.桶排序
算法步调
利用函数映射关系，将输入数据分到有限的桶里，然后每个通分别排序：
(1)初始化k个桶
(2)遍历数据，将数据放入到对应桶中
(3)每个桶单独排序
(4)各个桶的数据拼接起来
代码模板
https://i-blog.csdnimg.cn/direct/4b42624b81324655a6927564030d2523.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]