1.排序算法（学习自用）

1.冒泡排序

算法步调

相邻的元素之间对比，每次早出最大值或最小值放到最后或前面，所以形象的称为冒泡。
特点

n个数排序则举行n轮，每轮比力n-i次。所以时间复杂度为O(n^2)，空间复杂度为O(1)，该排序算法稳固。
代码模板

1. n = int(input())
2. a = list(map(int, input().split()))
4. for i in range(1, n-1):
5.     for j in range(0, n - i):
6.         if a[j] > a[j + 1]:
7.             a[j], a[j + 1] = a[j + 1], a[j]
9. print(' '.join(map(str, a)))

复制代码

2.选择排序

算法步调

从左往右找到最小元素，放在起始位置。依次找到第i个位置的元素。
特点

n个数排序有n个位置，每轮比力n-i次。所以时间复杂度为O(n^2)，空间复杂度为O(1)，该排序算法稳固。
代码模板

1. n = int(input())
2. a = list(map(int, input().split()))
4. for i in range(0, n-1):
5.     min_val = a[i]
6.     min_id = i
7.     for j in range(i, n):
8.         if a[j] < min_val:
9.             min_val = a[j]
10.             min_id = j
11.     a[i], a[min_id] = a[min_id], a[i]
13. print(' '.join(map(str, a)))

复制代码

3.插入排序

算法步调

第一个元素看做已排序，从左往右遍历每一个元素。在已排序元素中从后往前扫描：假如当前元素大于新元素，则钙元素移动到后一位。
简朴来说，对第i个元素从i向左到i-1找合适的位置插入。
特点

n个数排序则举行n轮插入，每轮比力i次。所以时间复杂度为O(n^2)，空间复杂度为O(1)，该排序算法不稳固。
代码模板

1. n = int(input())
2. a = list(map(int, input().split()))
4. for i in range(1, n):
5.     value = a[i]
6.     insert_id = 0
7.     for j in range(i - 1, -1, -1):
8.         if a[j] > value:
9.             a[j + 1] = a[j]
10.         else:
11.             insert_id = j + 1
12.             break
13.     a[insert_id] = value
15. print(' '.join(map(str, a)))

复制代码

4.快速排序

算法步调

找一个基准值x，把列表分为三部分：小于等于x的数、x、大于x的数字。左部分和右部分递归使用该计谋。
特点

时间复杂度为O(n log(n))，空间复杂度为O(n log(n))，该排序算法不稳固。
代码模板

1. def partition(a, left, right):
2.     id = left + 1
4.     for i in range(left + 1, right + 1):
5.         if a[i] <= a[left]:
6.             a[id], a[i] = a[i], a[id]
7.             id += 1
8.     a[left], a[id - 1] = a[id - 1], a[left]
9.     return id - 1
11. def quicksort(a, left, right):
12.     if left < right:
13.         mid = partition(a, left, right)
14.         quicksort(a, left, mid - 1)
15.         quicksort(a, mid + 1, right)
17. n = int(input())
18. a = list(map(int, input().split()))
20. quicksort(a, 0 , n - 1)
21. print(' '.join(map(str, a)))

复制代码

5.归并排序

算法步调

先把数组分成两部分，每部分递归处置惩罚酿成有序，将两个有序列表合并起来。
代码模板

1. n = int(input())
2. a = list(map(int, input().split()))
4. def merge(A,B):
5.     result = []
6.     while len(A)!=0 and len(B)!=0:
7.         if A[0] <= B[0]:
8.             result.append(A.pop(0))
9.         else:
10.             result.append(B.pop(0))
11.     result.extend(A)
12.     result.extend(B)
13.     return result
15. def mergesort(A):
16.     if len(A)<2:
17.         return A
18.     mid = len(A)//2
19.     left =mergesort(A[:mid])
20.     right = mergesort(A[mid:])
21.     return merge(left, right)
23. print(' '.join(map(str, mergesort(a))))

复制代码

6.桶排序

算法步调

利用函数映射关系，将输入数据分到有限的桶里，然后每个通分别排序：
(1)初始化k个桶
(2)遍历数据，将数据放入到对应桶中
(3)每个桶单独排序
(4)各个桶的数据拼接起来
代码模板

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。