文章目录
- 1.冒泡排序
- （1）基本逻辑
- （2）算法解析
- （3）完整版算法
- 1.从左向右比较，找最大值
- 2.从左向右比较，找最小值
- 3.优化方案
- （3）时间复杂度
- （4）冒泡排序的图形演示：
- 2.选择排序
- （1）基本逻辑
- （2）算法分步解析
- 1.从最左边找最小值的索引
- 2.从最右边找最大值的索引
- （3）完整算法
- 1.从左到右查找
- 2.从右向左查找
- （4）时间复杂度
- （5）选择排序演练
1.冒泡排序
（1）基本逻辑
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
冒泡排序算法的运作如下：
- 从左到右，依次比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最右边的元素肯定是所有数据里面的值最大的，对应的位置为（n-1）
- 除了最右边的一个元素，我们再针对其他所有的元素重复以上的步骤。再循环1次，我们就能找到所有元素里面第二大的数字了，排在倒数第二个位置（n-2）
- 持续如上的操作，在我们排序n-1次的时候，就能确定n-1个元素的具体位置，剩余一个元素也肯定是最小的了。此时排序确定的元素的索引为1
如下的数据，我们从左到右开始，先将相邻的两个元素比较，依次往右边移动比较，最终能找到所有数据里面最大的，如下图所示：
- 每一次需要比较的总次数，按照如下列表展示：
（2）算法解析
- 第一轮排序，找到最大值的位置需要排列到索引为n-1的位置（n为所有元素的数量）。
- 下一轮，我们就可以从索引为0开始，直到n-2之间做相邻2个比较了
- 最后一轮是index=1的元素，比较n-1次，就你能确定n个元素的排序位置了
# 如果我们只比较一轮，把最大的值放到列表最右边，可以如下方式
n
=
len
(
mylist
)
for
i
in
range
(
n
-
1
)
:
if
mylist
[
i
]
>
mylist
[
i
+
1
]
:
mylist
[
i
]
,
mylist
[
i
+
1
]
=
mylist
[
i
+
1
]
,
mylist
[
i
]
# 比较是从左向右开始比较的，但是最大值是放在最右边的
（3）完整版算法
1.从左向右比较，找最大值
def
bubble_sort
(
myList
)
:
n
=
len
(
myList
)
for
j
in
range
(
n
-
1
,
0
,
-
1
)
:
# 代表从最后一个元素向左到第二个元素，不包含index=0
for
i
in
range
(
j
)
:
# j代表其他需要比较的元素的索引，数量逐步减少
if
myList
[
i
]
>
myList
[
i
+
1
]
:
myList
[
i
]
,
myList
[
i
+
1
]
=
myList
[
i
+
1
]
,
myList
[
i
]
myList
=
[
54
,
26
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
bubble_sort
(
myList
)
print
(
myList
)
# [17, 20, 26, 31, 44, 54, 55, 77, 93]
最外面循环，代表找到每轮最大值的索引，从最右边，一直正数第二个元素，对应range（n-1， 0， -1）
里面循环，代表从第一个元素，到最大元素前面的那个元素，所以用rang（0， j）表示
2.从左向右比较，找最小值
def
maoPao_min
(
alist
)
:
n
=
len
(
alist
)
for
i
in
range
(
0
,
n
-
1
)
:
for
j
in
range
(
i
+
1
,
n
)
:
if
alist
[
i
]
>
alist
[
j
]
:
alist
[
j
]
,
alist
[
i
]
=
alist
[
i
]
,
alist
[
j
]
# [17, 20, 26, 31, 44, 54, 55, 77, 93]
3.优化方案
def
maoPao_min
(
alist
)
:
n
=
len
(
alist
)
for
i
in
range
(
0
,
n
-
1
)
:
isSorted
=
False
for
j
in
range
(
i
+
1
,
n
)
:
if
alist
[
i
]
>
alist
[
j
]
:
alist
[
j
]
,
alist
[
i
]
=
alist
[
i
]
,
alist
[
j
]
isSorted
=
True
print
(
"every time "
,
alist
)
if
not
isSorted
:
break
print
(
"result"
,
alist
)
myList
=
[
17
,
19
,
21
,
44
,
54
,
93
]
maoPao_min
(
myList
)
# every time [17, 19, 21, 44, 54, 93]
# result [17, 19, 21, 44, 54, 93]
当排序到某个位置的时候，后面的所有其他元素排序都排好了。那么循环的话，一次都不需要置换元素，这种情况我们可以做个判断，直接跳过所有循环即可
（3）时间复杂度
- 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
- 最坏时间复杂度：O(n²)
- 稳定性：稳定
（4）冒泡排序的图形演示：
2.选择排序
（1）基本逻辑
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：
- 首先，假设最左边元素为最小值(min_index = 0)
- 其次，假设的最小值和其他元素比较，从左到右，相邻2个元素依次比较大小，最终找到最小值的索引
- 然后，判断假设的最小值的索引是否与真实的最小值的索引一样，不一样就直接互换元素的位置，这样第一次循环就确定了所有元素中最小值的位置
- 最后，紧接着假设min_index = 1,依次重复如上步骤，找到其余元素中的最小值，直到假设的最小索引为倒数第二个元素的索引为止（倒数第二个与最后一个比较一次就结束了）
选择排序的主要优点:
- 每次循环一遍，比较完所有元素之后，找到最小（大）值之后，才会互换位置，否者不会互换位置
- 如果某个元素位于正确的最终位置上，则它不会被移动
- 如果列表为n个元素，那么所有元素最多进行n-1次交换（每个元素都换到非自己本身的位置）
- 如果所有元素都需要移动位置，选择排序属于非常好的一种
下图是每次找到最小值的索引，然后替换：
如下图是每次找到一个最大值的索引，然后替换：
（2）算法分步解析
1.从最左边找最小值的索引
alist
=
[
54
,
226
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
def
choiceSort
(
alist
)
:
n
=
len
(
alist
)
min_index
=
0
# 假设最左边为最小值
for
i
in
range
(
1
,
n
)
:
# 需要拿最小索引右边的所有元素与假设的比较
if
alist
[
min_index
]
>
alist
[
i
]
:
min_index
=
i
if
min_index
!=
0
:
alist
[
min_index
]
,
alist
[
0
]
=
alist
[
0
]
,
alist
[
min_index
]
choiceSort
(
alist
)
print
(
alist
)
# result [17, 226, 93, 54, 77, 31, 44, 55, 20]
2.从最右边找最大值的索引
alist
=
[
54
,
226
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
def
choiceSort
(
alist
)
:
n
=
len
(
alist
)
max_index
=
n
-
1
# 假设最右边为最大值的索引
for
i
in
range
(
n
-
2
,
-
1
,
-
1
)
:
# 需要拿倒数第二个索引，从右向左比较，直到第一个索引
if
alist
[
max_index
]
<
alist
[
i
]
:
max_index
=
i
if
max_index
!=
n
-
1
:
alist
[
max_index
]
,
alist
[
n
-
1
]
=
alist
[
n
-
1
]
,
alist
[
max_index
]
choiceSort
(
alist
)
print
(
alist
)
# result [54, 20, 93, 17, 77, 31, 44, 55, 226]
注意点：
- 从左到右找的时候，第二个索引到最后一个索引的表达式：range（2，n-1）
- 从右向左找的时候，倒数第二个索引，到正数第一个索引的表达式：range（n-2，-1，-1）
（3）完整算法
1.从左到右查找
def
selection_sort
(
alist
)
:
n
=
len
(
alist
)
# 需要进行n-1次选择操作
for
i
in
range
(
n
-
1
)
:
min_index
=
i
# 记录最小位置
for
j
in
range
(
i
+
1
,
n
)
:
# 从i+1位置到末尾选择出最小数据
if
alist
[
j
]
<
alist
[
min_index
]
:
min_index
=
j
if
min_index
!=
i
:
alist
[
i
]
,
alist
[
min_index
]
=
alist
[
min_index
]
,
alist
[
i
]
alist
=
[
54
,
226
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
selection_sort
(
alist
)
print
(
alist
)
# [17, 20, 31, 44, 54, 55, 77, 93, 226]
2.从右向左查找
def
selection_sort
(
alist
)
:
n
=
len
(
alist
)
# 需要进行n-1次选择操作
for
i
in
range
(
n
-
1
,
0
,
-
1
)
:
max_index
=
i
# 记录最大值的索引
for
j
in
range
(
i
-
1
,
-
1
,
-
1
)
:
# 从i-1位置到起始位置选择出最大值索引
if
alist
[
j
]
>
alist
[
max_index
]
:
max_index
=
j
# 如果选择出的数据不在正确位置，进行交换
if
max_index
!=
i
:
alist
[
i
]
,
alist
[
max_index
]
=
alist
[
max_index
]
,
alist
[
i
]
selection_sort
(
alist
)
print
(
alist
)
# [17, 20, 31, 44, 54, 55, 77, 93, 226]
注意点：
从左到右假设最小值索引的时候：0--------n-2， 对应range(n-1)，到倒数第二个元素
此时，需要与其比较的其他数据的索引为：0+1------------n-1，对应的range（1， n）从第二个元素到最后一个元素
从右向左排序的时候，假设最右边为最大值索引，n-1----------1，对应range(n-1, 0, -1)
此时，需要比较的其他元素的索引为：n-2--------0,对应的range(n-2, -1, -1)
（4）时间复杂度
- 最优时间复杂度：O(n²)
- 最坏时间复杂度：O(n²)
- 稳定性：不稳定（考虑升序每次选择最大的情况）
（5）选择排序演练
