参考链接:
https://www.cnblogs.com/fivestudy/p/10212306.html
https://blog.csdn.net/qq_43549984/article/details/89426394#Bubble_Sort_21
1.排序算法是什么?
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序。
- 内部排序是数据记录在内存中进行排序。
- 外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
常见的内部排序算法有:冒泡,插入,归并,选择,快排,希尔,堆排序,基数排序等。
Algorithm算法 | Time Complexity时间复杂度 | Space Complexity空间复杂度 | |||
---|---|---|---|---|---|
Best | Average | Worst | Worst | 稳定性 | |
QuickSort 快排 | O(n log(n)) | O(n log(n)) | O(n^2) | O(n log(n)) | 不稳定 |
MergeSort 归并 | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) | 稳定 |
BubbleSort 冒泡 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
InsertionSort 插入 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
SelectionSort 选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
2.时间复杂度
平方阶 | O(n^2) | 插入 | 选择 | 冒泡 |
---|---|---|---|---|
线性对数阶 | O(n log(n)) | 快排 | 归并 | 堆排序 |
线性阶 | O(n) | 基数排序 | 桶排序 | 箱排序 |
3.稳定性
稳定 | 冒泡 | 插入 | 归并 | 基数 |
---|---|---|---|---|
不稳定 | 选择 | 快排 | 希尔 | 堆排序 |
4.冒泡排序
Bubble Sort是一种简单的排序算法,它反复遍历列表,比较相邻的两个元素,如果顺序不对,则交换它们。该算法是一种比较排序,它是以较小或较大元素“冒泡”到列表顶部的方式命名的。虽然算法很简单,但对于大多数问题来说,它太慢了。
4.1-算法步骤解析
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了已经排序好的。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
4.2-图解
4.3-代码
"""
def bubble_sort(alist):
# 方式1
for i in range(len(alist)-1):
for j in range(len(alist)-1-i):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
return alist
"""
def bubble_sort(alist):
# 方式2
for i in range(len(alist)-1):
flag = True
for j in range(len(alist)-1-i):
if alist[j] > alist[j + 1]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
flag = False
if flag is True:
break
return alist
def test_bubble_sort():
import random
alist = list(range(10))
random.shuffle(alist)
result = bubble_sort(alist)
print(result)
test_bubble_sort()
4.4-解析
一、方式1
- n-1轮循环
- 在每一轮循环中,不管相邻元素的大小是否已经有序。都会进行大小对比。
- 递归的不断判断,经过n-1轮查询后,得到最终结果。
二、方式2
- n-1轮查询
- 每一轮查询,相邻元素判断大小之前,立flag:指默认 不需要替换。每一次进入循环后,如果有满足条件相邻元素前面大于后面,那么便交换数据,且更改flag为false,直到本轮循环结束。
- 下一轮循环开始,初始化flag,当本轮循环如果所有相邻元素都满足顺序(升序或者降序),便跳出本轮循环。
- 当初始默认参数是(升序或降序时),经过n轮外循环,内循环只执行break1次,便跳出循环,最优时间复杂度便为O(n)。最坏情况,便是内循环也需要执行n次,最坏时间复杂度为O(n^2)。
5.选择排序
Selection Sort是一种就地比较排序算法,时间复杂度O(n^2) ,因此它在大型列表中效率比较低下。
但该算法以其简单性著称,在某些情况下,它比更复杂的算法具有性能优势,特别是当辅助内存有限的时候。
Selection Sort将输入列表分为两部分:已排序子列表(在列表的前端),以及待排序子列表。最初,已排序子列表是空的,未排序子列表是整个列表。算法通过在待排序子列表中查找最小的元素,将其与最左边的待排序元素交换,并将已排序子列表边界向右移动一个元素来继续。
5.1-算法步骤解析
- 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
5.2-图解
5.3-代码
def select_sort(alist):
for i in range(len(alist)):
min_num = i
for j in range(i+1, len(alist)):
if alist[j] < alist[min_num]:
min_num = j
alist[i], alist[min_num] = alist[min_num], alist[i]
return alist
5.4-解析
- 循环从未排序列表中找到最小值(和已经排序列表的最后一个值对比大小),和已排序列表最后一个值交换。
- 初始列表中找第一个最小值,设置默认初值,所以需要外循环len(alist)
- 设置最小值默认处置为外循环的变量i
- 内循环选择最小(和初始值对比最小)的元素,如果找到则更新最小值的下标,直到本轮内循环结束,将最小值与初始值交换;如果直到本轮内循环结束还未找到,开始下一轮外循环。
6.插入排序
Insertion Sort是一种简单的排序算法,它只需要一次遍历即可生成最终排序的数组。它在大列表中的效率比更高级的算法低,但是,它有以下几个优点:
一、实现简单,几行代码即可完成。
二、对(相当)小的数据集很有效。
三、在实践中比其他简单的O(n^2) 算法更有效。
四、自适应,当输入中的每个元素离其最终位置不超过 k时,时间复杂度仅 O(kn)。
五、稳定,不改变具有相等值的元素的相对顺序。
六、空间复杂度低,仅 O(1) 。
七、在线算法,可以边读边排序,不需要先读取全部数组。
6.1-算法步骤解析
- 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
6.2-图解
6.3-代码
def insert_sort(alist):
for i in range(1, len(alist)):
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
else:
break
return alist
6.4-解析
抽象分析:
还是当我们玩牌时,怎么整理牌最快?
- 我们以第一张牌为初始值
- 第一轮循环判断,判断第2张牌是否比第一张大,没有则交换顺序,有则位置不动,跳出本轮循环。
- 第二轮循环,判断第3张牌是后比第二张大,没有则交换顺序,有则位置不动;在与第1张牌对比,如果没有第1张牌大,则继续交换顺序,有则位置不动。跳出本轮循环。
- 以此类推,经过n-1轮循环后,得到最终结果。
时间复杂度:
best:O(n)
worst:O(n^2)
关键在于代码中的else, break
。当列表顺序已经是升序或降序了,比较两个元素大小时不满足交换条件,说明该元素比前一个元素大或者小,由于前一个元素比它之前的所有元素都大或小,所有便可以跳出本次循环。相当于经过n轮循环,每次循环都只执行一次break,所以最优时间复杂度为O(n)。
7.归并排序
Merge sort是一种高效、通用、基于比较的排序算法,该算法利用了分治的思想,将规模较大的排序问题化归到较小的规模上解决。
Merge sort的步骤如下:
一、将未排序的列表划分为两个元素数量相同的子数组。
二、排序这两个子数组,再将它们进行合并。
7.1-定义
归并排序是分而治之算法,先分,在组合(组合前进行对比大小排序)。主要两个步骤。
- 连续划分未排序列表,直到有N个子列表,其中每个子列表有1个“未排序”元素,N是原始数组中的元素数。
- 重复合并,即一次将两个子列表合并在一起,生成新的排序子列表,直到所有元素完全合并到一个排序数组中。
7.2-图解
7.3-代码实现
# coding:utf-8
def merge_sort(alist):
num = len(alist)
if num == 1:
return alist
mid = num // 2
left_li = merge_sort(alist[:mid])
right_li = merge_sort(alist[mid:])
left_pointer, right_pointer = 0, 0
result = []
while left_pointer < len(left_li) and right_pointer < len(right_li):
if left_li[left_pointer] < right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer += 1
else:
result.append(right_li[right_pointer])
right_pointer += 1
result += left_li[left_pointer:]
result += right_li[right_pointer:]
return result
result2 = merge_sort([1, 8, 7, 3, 5, 6, 4, 2, 9])
print(result2)
7.4-解析
- 拆分:直到拆分结果是独立个体,个体长度为1时,准备合并。
- 设置全局变量接受合并后的结果
- 设定左指针和右指针的初始值为0
- 设定循环判断条件左右指针长度必须小于拆分后的左右列表的长度(and与条件)。(防止列表取值超出指针可索引范围),当不符合条件时,跳出循环。
- 合并:根据指针值对左右列表的值对比大小。小的先存入全局变量合并结果内,且相应的拆分列表指针+=1
- 当某一个拆分列表的值全部存储合并结果后,该拆分列表的指针值达到最大可索引值。另外一个拆分列表,在5步中对比大小时肯定比已经存入合并结果的值大,且该拆分列表也是有序状态的,所以可以直接在已经合并结果的基础上,加上该拆分列表的指针值到最后的所有元素。(注意:当某一个拆分列表指针值达到最大时,取该指针值到最后的结果是空列表,例如a = [0,1,2,3],而a[4:]的值是空列表)
- 返回结果
时间复杂度:
best:O(n log(n))
worst:O(n log(n))
7.5-代码运行步骤
def merge_sort([1, 8, 7, 3, 5, 6, 4, 2]):
mid = 4
left_li = def merge_sort([1, 8, 7, 3]):
mid = 2
left_li = def merge_sort([1, 8]):
mid = 1
left_li = def merge_sort([1]):
return alist # 到这里第7含的merge函数执行完毕(得到结果left_li=[1]),第7行的函数知识第5含函数的一含代码,继续向下执行.
right_li = def merge_sort([8]):
return alist # 同第8行代码一样,第9含的函数也是第5含代码函数的一行代码,得到结果right_li=[8]),继续向下执行.
# 左右指针=0
# result = []
# 循环判断
result= [1], 左指针 = 1, 右指针 = 0
result = [1] + [] = [1]
result = [1] + [8] = [1,8]
return result # 到这里第5行代码执行完毕,得到结果left_li = [1, 8]
right_li = def merge_sort([7, 3]):
mid = 1
left_li = [7]
right_li = [3]
# 左右指针=0
# result = []
# 循环判断
result= [3], 右指针 = 1, 左指针 = 0
result = [3] + [] = [3]
result = [3] + [7] = [3,7]
return result # 到这里第18行代码执行完毕,得到结果right_li = [3, 7]
left_li = [1, 8]
right_li = [3, 7]
# 左右指针=0
# result = []
# 循环判断
result= [1], 左指针 = 1, 右指针 = 0
result= [1,3], 右指针 = 1, 左指针 = 1
result= [1,3,7], 右指针 = 2, 左指针 = 1
result = [1,3,7] + [8] = [1,3,7,8]
result = [1,3,7,8] + [] = [1,3,7,8]
return result # 到这里第3行代码执行完毕,得到结果left_li = [1,3,7,8]
right_li = def merge_sort([5,6,4,2]):
# 执行步骤同第4行到第39行代码一样.
return result # 到这里第40行代码执行完毕,得到结果right_li = [2,4,5,6]
left_li = [1,3,7,8]
right_li = [2,4,5,6]
# 左右指针=0
# result = []
# 循环判断
result= [1], 左指针 = 1, 右指针 = 0
result= [1,2], 右指针 = 1, 左指针 = 1
result= [1,2,3], 左指针 = 2, 右指针 = 1
result= [1,2,3,4], 左指针 = 2, 右指针 = 2
result= [1,2,3,4,5], 右指针 = 3, 左指针 = 2
result= [1,2,3,4,5,6], 右指针 = 4, 左指针 = 2
# 到这里右指针 = 4, 左指针 = 2, 不满足循环条件,
result = [1,2,3,4,5,6] + [7,8] = [1,2,3,4,5,6,7,8]
result = [1,2,3,4,5,6,7,8] + [] = [1,2,3,4,5,6,7,8]
return result # 到这里第1行代码执行完毕,得到结果result = [1,2,3,4,5,6,7,8]
8.快速排序
8.1-定义
快速排序也是一种分而治之的算法,如归并排序。虽然它有点复杂,但在大多数标准实现中,它的执行速度明显快于归并排序,并且很少达到最坏情况下的复杂度O(n) 。它有三个主要步骤:
- 从数组中选择一个元素,称为pivot。
- 对数组进行排序,使所有小于pivot的元素都位于pivot之前,而所有值大于pivot的元素都位于pivot之后(相等的值可以朝任何方向移动)。这一步操作通常称为partition。
- 递归地将上述步骤应用于pivot之前和之后的子数组。
递归的基本情况是大小为0或1的数组,它们是按定义排列的,因此不需要对它们进行排序。
8.2-图解
8.3-代码实现
方式1:
def quick_sort(alist):
if len(alist) < 2: # 递归出口,当数组是空数组或者只有一个元素的数组都是有序的。
return alist
else:
pivot_index = 0
pivot = alist[pivot_index]
less_part = [i for i in alist[pivot_index+1:] if i <= pivot]
great_part = [i for i in alist[pivot_index+1:] if i > pivot]
return quick_sort(less_part) + [pivot] + quick_sort(great_part)
方式2:
def quick_sort(li, start, end):
if start >= end:
return
l_pointer = start
r_pointer = end
pivot = li[l_pointer]
while l_pointer < r_pointer:
while l_pointer < r_pointer and li[r_pointer] >= pivot:
r_pointer -= 1
li[l_pointer], li[r_pointer] = li[r_pointer], li[l_pointer]
while l_pointer < r_pointer and li[l_pointer] < pivot:
l_pointer += 1
li[l_pointer], li[r_pointer] = li[r_pointer], li[l_pointer]
li[l_pointer] = pivot
quick_sort(li, start, l_pointer - 1)
quick_sort(li, l_pointer + 1, end)