1.快速排序
a.原理
快速排序的基本思想是在待排序的 n 个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放人最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称为划分。然后对两个子序列分别重复上述过程，直到每个子序列内只有一个元素或空为止。
这是一种二分法思想，每次将整个无序序列一分为二。归位一个元素，对两个子序列采用同样的方式进行排序，直到子序列的长度为1或0为止。（摘自算法分析与设计第二版 有删改）
b.代码
-
def quick_
sort(arr):
-
if len(arr)
<=
1:
-
return arr
-
pivot
= arr[len(arr)
/
/
2]#轴
-
left
= [x
for x
in arr
if x
< pivot]
-
middle
= [x
for x
in arr
if x
=
= pivot]
-
right
= [x
for x
in arr
if x
> pivot]
-
return quick_
sort(
left)
+ middle
+ quick_
sort(
right)
-
s
= list(map(float,
input(
"输入用空格分隔的数字：").split()))#
-
print(quick_
sort(s))
2.插入排序
a.原理
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
b.代码
-
def insert_
sort(arr):
-
for i
in range(
1, len(arr)):
-
key
= arr[i]
-
j
= i
-
1
-
while j
>=
0
and arr[j]
>
key:
-
arr[j
+
1]
= arr[j]
-
j -
=
1
-
arr[j
+
1]
=
key
-
return arr
-
-
arr
= [
3,
5,
2,
4,
1]
-
print(insert_
sort(arr))
3.冒泡排序
a.原理
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成
b.代码
-
def bubble_
sort(arr):
-
for i
in range(len(arr)):
-
for j
in range(len(arr)
- i
-
1):
-
if arr[j]
> arr[j
+
1]:
-
arr[j], arr[j
+
1]
= arr[j
+
1], arr[j]
-
return arr
-
-
arr
= [
3,
5,
2,
4,
1]
-
print(bubble_
sort(arr))
4.希尔排序
a.原理
希尔排序是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
b.代码
-
def shell_
sort(arr):
-
n
= len(arr)
-
gap
= n
/
/
2
-
while gap
>
0:
-
for i
in range(gap, n):
-
temp
= arr[i]
-
j
= i
-
while j
>= gap
and arr[j
- gap]
> temp:
-
arr[j]
= arr[j
- gap]
-
j -
= gap
-
arr[j]
= temp
-
gap
/
/
=
2
-
return arr
-
-
arr
= [
3,
5,
2,
4,
1]
-
print(shell_
sort(arr))
5.选择排序
a.原理
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法
b.代码
-
def selection_
sort(arr):
-
for i
in range(len(arr)):
-
min_
index
= i
-
for j
in range(i
+
1, len(arr)):
-
if arr[min_
index]
> arr[j]:
-
min_
index
= j
-
arr[i], arr[min_
index]
= arr[min_
index], arr[i]
-
return arr
-
-
arr
= [
3,
5,
2,
4,
1]
-
print(selection_
sort(arr))
6.堆排序
a.原理
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
发明人：罗伯特·弗洛伊德
b.代码
-
def heap_
sort(arr):
-
n
= len(arr)
-
# 建立大顶堆
-
for i
in range(n
/
/
2
-
1, -
1, -
1):
-
heapify(arr, n, i)
-
# 将堆顶元素与末尾元素交换，并重新调整大顶堆
-
for i
in range(n
-
1,
0, -
1):
-
arr[i], arr[
0]
= arr[
0], arr[i]
-
heapify(arr, i,
0)
-
return arr
-
-
def heapify(arr, n, i):
-
largest
= i
-
l
=
2
* i
+
1
-
r
=
2
* i
+
2
-
if l
< n
and arr[largest]
< arr[l]:
-
largest
= l
-
if r
< n
and arr[largest]
< arr[r]:
-
largest
= r
-
if largest !
= i:
-
arr[i], arr[largest]
= arr[largest], arr[i]
-
heapify(arr, n, largest)
-
-
arr
= [
3,
5,
2,
4,
1]
-
print(heap_
sort(arr))
7.归并排序
a.原理
归并排序的基本思想是首先将 a [0.. n 一1］看成 n 个长度为1的有序表，将相邻的 k ( k ≥2）个有序子表成对归并，得到 n / k 个长度为 k 的有序子表：然后再将这些有序子表继续归并，得到 n /k2个长度为 k 的有序子表，如此反复进行下去，最后得到一个长度为 n 的有序表。由于整个排序结果放在一个数组中，所以不需要特别地进行合并操作。若 k =2，即归并是在相邻的两个有序子表中进行的，称为二路归并排序。若 k >2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。（摘自算法分析与设计第二版）
b.代码
-
def merge_
sort(arr):
-
if len(arr)
>
1:
-
mid
= len(arr)
/
/
2
-
left
= arr[:mid]
-
right
= arr[mid:]
-
merge_
sort(
left)
-
merge_
sort(
right)
-
-
i
= j
= k
=
0
-
-
while i
< len(
left)
and j
< len(
right):
-
if
left[i]
<
right[j]:
-
arr[k]
=
left[i]
-
i
+
=
1
-
else:
-
arr[k]
=
right[j]
-
j
+
=
1
-
k
+
=
1
-
-
while i
< len(
left):
-
arr[k]
=
left[i]
-
i
+
=
1
-
k
+
=
1
-
-
while j
< len(
right):
-
arr[k]
=
right[j]
-
j
+
=
1
-
k
+
=
1
-
-
arr
= [
12,
11,
13,
5,
6,
7]
-
merge_
sort(arr)
-
print(arr)
-
有待补充。
转载：https://blog.csdn.net/weixin_53197693/article/details/129175886