没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
94页
冒泡排序(Bubble Sort) 选择排序(Selection Sort) 插入排序(Insertion Sort) 希尔排序(Shell Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 计数排序(Counting Sort) 基数排序(Radix Sort) 桶排序(Bucket Sort) 深度优先搜索(Depth-First Search, DFS) 广度优先搜索(Breadth-First Search, BFS) 二分查找(Binary Search) 线性查找(Linear Search) 素字符串匹配算法(Naive String Matching) KMP 算法(Knuth-Morris-Pratt) Rabin-Karp 算法 Boyer-Moore 算法 A* 搜索算法 Dijkstra 算法 Bellman-Ford 算法 Floyd-Warshall 算法 Kruskal 算法 Prim 算法 Edmonds-Karp 算法 Ford-Fulkerson 算法
资源推荐
资源详情
资源评论
常⽤算法
!
冒泡排序(Bubble Sort)
!
冒泡排序(Bubble Sort)是⼀种简单的排序算法。它重复地遍历待排序的列表,⽐较每对相邻的
元素,并在必要时交换它们。这个过程会⼀直重复,直到整个列表完全排序。因为较⼩的元素会像
⽓泡⼀样逐渐浮到列表的顶部,所以被称为冒泡排序。
冒泡排序的时间复杂度为 O(n^2),因此在⼤型数据集上效率较低。然⽽,对于⼩型数据集或部分
有序的数据,它可能是⼀个合适的选择。
以下是⼀个使⽤ Python 实现的冒泡排序示例:
在这个示例中,bubble_sort 函数接受⼀个列表 arr 作为参数。它⾸先获取列表的⻓度,然后使⽤
两个嵌套循环遍历列表。外层循环负责跟踪已排序的元素数量,⽽内层循环则负责逐个⽐较相邻元
素并在需要时交换它们。
选择排序(Selection Sort)
!
选择排序(Selection Sort)是⼀种简单的排序算法。它的⼯作原理是在每次遍历中,从未排序的
部分找到最⼩(或最⼤)的元素,然后将其放到正确的位置。这个过程会⼀直重复,直到整个列表
完全排序。
选择排序的时间复杂度为 O(n^2),因此在⼤型数据集上效率较低。然⽽,对于⼩型数据集,它可
能是⼀个合适的选择。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 将最⼤的元素移到数组的末尾
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
bubble_sort(arr)
print("排序后的数组:", arr)
以下是⼀个使⽤ Python 实现的选择排序示例:
在这个示例中,selection_sort 函数接受⼀个列表 arr 作为参数。它⾸先获取列表的⻓度,然后使
⽤⼀个循环遍历列表。在每次循环中,⾸先假设当前元素是最⼩的元素。然后,使⽤另⼀个循环从
未排序的部分中查找最⼩元素的实际索引。最后,将找到的最⼩元素与当前元素交换位置。这个过
程会⼀直重复,直到整个列表完全排序。
插⼊排序(Insertion Sort)
!
插⼊排序(Insertion Sort)是⼀种简单的排序算法。它的⼯作原理是将未排序的元素插⼊到已排序
部分的正确位置,以便使已排序部分保持有序状态。这个过程会⼀直重复,直到整个列表完全排
序。
插⼊排序的时间复杂度为 O(n^2),因此在⼤型数据集上效率较低。然⽽,对于⼩型数据集或部分
有序的数据,它可能是⼀个合适的选择。
以下是⼀个使⽤ Python 实现的插⼊排序示例:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
# 找到从 i 开始的最⼩元素的索引
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 将找到的最⼩元素交换到正确的位置
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
selection_sort(arr)
print("排序后的数组:", arr)
def insertion_sort(arr):
n = len(arr)
# 从第⼆个元素开始插⼊
for i in range(1, n):
key = arr[i]
j = i - 1
# 从右向左扫描已排序的部分
在这个示例中,insertion_sort 函数接受⼀个列表 arr 作为参数。它⾸先获取列表的⻓度,然后使
⽤⼀个循环遍历列表。在每次循环中,将当前元素插⼊到已排序部分的正确位置。要插⼊⼀个元
素,需要从右向左扫描已排序部分并找到合适的位置。在找到正确的位置之后,将未排序的元素插
⼊到正确的位置。这个过程会⼀直重复,直到整个列表完全排序
希尔排序(Shell Sort)
!
希尔排序(Shell Sort)是⼀种排序算法,是插⼊排序的⼀种变体。它通过将列表分成较⼩的⼦列
表来改善插⼊排序的效率,并对每个⼦列表使⽤插⼊排序算法来排序。由于⼦列表是相对较⼩的,
因此插⼊排序在这些⼦列表上的⼯作效率更⾼。随着算法的执⾏,它逐渐减少⼦列表的⼤⼩,最终
达到对整个列表进⾏插⼊排序的阶段。
希尔排序的时间复杂度取决于所使⽤的增量序列。理论上,最坏情况下的时间复杂度为 O(n^2),
但在实际使⽤中,它通常表现得⽐实际上更快。
以下是⼀个使⽤ Python 实现的希尔排序示例:
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# 插⼊未排序部分的正确位置
arr[j + 1] = key
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
insertion_sort(arr)
print("排序后的数组:", arr)
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
在这个示例中,shell_sort 函数接受⼀个列表 arr 作为参数。它⾸先获取列表的⻓度,然后使⽤⼀
个循环遍历列表。在每次循环中,⽣成⼀个增量序列,并将列表分成多个⼦列表。然后对每个⼦列
表使⽤插⼊排序算法来排序。插⼊排序的实现与常规插⼊排序类似,但是插⼊排序的循环被修改为
使⽤增量来移动元素。最后,减⼩增量并重复该过程,直到增量为 1,表示整个列表已经排序完
成。
!
希尔排序(Shell Sort)是⼀种排序算法,是插⼊排序的⼀种变体。它通过将列表分成较⼩的⼦列
表来改善插⼊排序的效率,并对每个⼦列表使⽤插⼊排序算法来排序。由于⼦列表是相对较⼩的,
因此插⼊排序在这些⼦列表上的⼯作效率更⾼。随着算法的执⾏,它逐渐减少⼦列表的⼤⼩,最终
达到对整个列表进⾏插⼊排序的阶段。
希尔排序的时间复杂度取决于所使⽤的增量序列。理论上,最坏情况下的时间复杂度为 O(n^2),
但在实际使⽤中,它通常表现得⽐实际上更快。
以下是⼀个使⽤ Python 实现的希尔排序示例:
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
shell_sort(arr)
print("排序后的数组:", arr)
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
# 示例
在这个示例中,shell_sort 函数接受⼀个列表 arr 作为参数。它⾸先获取列表的⻓度,然后使⽤⼀
个循环遍历列表。在每次循环中,⽣成⼀个增量序列,并将列表分成多个⼦列表。然后对每个⼦列
表使⽤插⼊排序算法来排序。插⼊排序的实现与常规插⼊排序类似,但是插⼊排序的循环被修改为
使⽤增量来移动元素。最后,减⼩增量并重复该过程,直到增量为 1,表示整个列表已经排序完
成。
归并排序(Merge Sort)
!
归并排序(Merge Sort)是⼀种基于分治思想的排序算法。它的核⼼思想是将待排序的列表分成较
⼩的⼦列表,然后递归地排序这些⼦列表,最后将它们合并以创建排序后的列表。归并排序在处理
⼤型数据集时表现出⾊,但在实现时需要额外的空间来保存⼦列表。
归并排序的时间复杂度为 O(n log n),并且是稳定排序算法,因此在需要稳定排序的情况下,归并
排序是⼀个很好的选择。
以下是⼀个使⽤ Python 实现的归并排序示例:
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
shell_sort(arr)
print("排序后的数组:", arr)
def merge_sort(arr):
n = len(arr)
if n > 1:
# 分割列表
mid = n // 2
left_half = arr[:mid]
right_half = arr[mid:]
# 递归排序⼦列表
merge_sort(left_half)
merge_sort(right_half)
# 合并两个有序⼦列表
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
剩余93页未读,继续阅读
资源评论
qq_25426809
- 粉丝: 1
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功