男女第一次做网站爱,小程序开发平台软件,自己做自媒体在哪个网站比较好,做透明头像的网站参考资料#xff1a;
《Python实现5大排序算法》《六大排序算法#xff1a;插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序》 --代码似乎是C语言
———————— 本文介绍5种常见的排序算法和基于Python实现#xff1a; 冒泡排序#xff08;Bubble Sort
《Python实现5大排序算法》《六大排序算法插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序》 --代码似乎是C语言
———————— 本文介绍5种常见的排序算法和基于Python实现 冒泡排序Bubble Sort通过不断交换相邻元素将较大的元素逐渐“冒泡”到数组的尾部较小的元素逐渐沉到数组的头部。 选择排序Selection Sort每次从未排序的部分中选择最小或最大的元素然后放到已排序部分的末尾或开头。 插入排序Insertion Sort将数组分为已排序和未排序两部分逐个将未排序元素插入到已排序部分的适当位置使其保持有序。 快速排序Quick Sort通过递归地选择一个基准元素并将数组划分为小于基准和大于基准的两部分然后对两部分继续进行快速排序。 归并排序Merge Sort将数组拆分成两个子数组对每个子数组进行排序然后再将两个有序子数组合并成一个有序数组。 不同的排序算法在时间复杂度、空间复杂度以及稳定性等方面有所不同选择适合具体情况的排序算法可以提高排序效率。
一、冒泡排序
冒泡排序是一种简单的排序算法它的思想是重复地走访过要排序的元素列依次比较相邻的两个元素如果它们的顺序错误就交换它们直到没有任何再需要交换的元素排序完成。 案例 我们以升序为实例。【34,64,11,12,22,25,90】长度为7. 第一次循环要判断交换n-1次6.两两交换要将最大值90沉到末尾。结果为【34,11,12,22,25,64,90】
第二次循环要判断n-2次5.两两交换要将次最大值64沉到尾部(90之前)。结果为 【11,12,22,25,34,64,90】 第三次循环要判断n-3次4. 值得注意的是在这次循环中没有一次交换行为。 第四次循环要判断n-4次3.值得注意的是在这次循环中没有一次交换行为。 第五次循环要判断n-5次2.值得注意的是在这次循环中没有一次交换行为。 第六次循环要判断n-6次1.值得注意的是在这次循环中没有一次交换行为。
因此设置一个“标志位”用于优化。若某次循环中没有交换元素说明数组已经有序可以提前结束排序。即在第三次循环中判断没有交换则可以提前结束优化了。
1.1 代码
def bubble_sort(arr):n len(arr)for i in range(n - 1):# 标志位用于优化若某次循环中没有交换元素说明数组已经有序可以提前结束排序swapped Falsefor j in range(n - i - 1):if arr[j] arr[j 1]:arr[j], arr[j 1] arr[j 1], arr[j]swapped Trueif not swapped:break
测试
# 使用示例
arr [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # 输出[11, 12, 22, 25, 34, 64, 90]
在冒泡排序中外层循环控制需要比较的次数内层循环实际进行相邻元素的比较和交换。通过标志位swapped的引入可以优化冒泡排序当某次循环没有发生交换时说明数组已经有序可以提前结束排序。这样在数组近乎有序的情况下冒泡排序的性能会有所提升。
改进 “swapped”是优化的循环次数提前截止循环。当序列的长度足够大的时候在循环的某次的内部是否可以提前截止交换呢 【22,12,1125, 34,64 90】 假设如果我们用last_swap_index记录当前轮次最后交换的位置。在下一轮的循环的时候提前结束判断交换。则在每个循环轮次中节省很多判断和步骤。因此优化后的代码为
1.2 优化后的代码
def bubble_sort(arr):n len(arr)for i in range(n - 1):swapped False# 记录当前轮循环最后一次交换的位置初始值为未排序部分的末尾last_swap_index n - 1for j in range(n - i - 1):if arr[j] arr[j 1]:arr[j], arr[j 1] arr[j 1], arr[j]swapped Truelast_swap_index j # 更新最后一次交换的位置if not swapped:break# 更新下一轮未排序部分的边界n last_swap_index 11.3 复杂度
时间复杂度最坏情况O(N^2) 最好情况O(N) 空间复杂度O(1)
二、选择排序
选择排序Selection Sort是一种简单直观的排序算法其思想是在未排序部分找到最小或最大元素然后与未排序部分的第一个元素交换位置。重复这个过程直到所有元素都有序。
2.1 代码
def selection_sort(arr):n len(arr)for i in range(n - 1):# 假设当前未排序部分的第一个元素是最小的min_idx 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]
selection_sort(arr)
print(arr) # 输出[11, 12, 22, 25, 34, 64, 90]在选择排序中外层循环控制需要排序的次数内层循环在未排序部分中找到最小元素的索引。然后将找到的最小元素与未排序部分的第一个元素交换位置。这样每一轮循环会将未排序部分的最小元素放到已排序部分的末尾从而实现排序。选择排序的时间复杂度是O(n^2)它是一个不稳定的排序算法。 改进 换个角度看外层循环指示了已排序部分的末尾要求所有的元素都必须经历排序因此外层循环是不可能像冒泡排序一样提前截止的。在每次循环的内部选择最小元素的时候我们也必须在所有未排序的元素中选择也不可以提前截止。因此我们只能将优化的注意力放在“交换”上。 例如:【11,12,22,25,34,90,64】 第一次循环位置arr[0], 选择最小的arr[0]–交换 第二次循环位置arr[1], 选择最小的arr[1]–交换 第二次循环位置arr[2], 选择最小的arr[2]–交换 。。。 可以看到出现了很多不必要的交换。因此添加一个判断因素从而停止交换。—提醒的是计算机做判断的消耗的运行时间远远小于数组的位置交换所消耗的时间。
2.2 优化的代码
def selection_sort(arr):n len(arr)for i in range(n - 1):min_idx ifor j in range(i 1, n):if arr[j] arr[min_idx]:min_idx j# 如果最小元素的索引不是当前的第一个元素才进行交换if min_idx ! i:arr[i], arr[min_idx] arr[min_idx], arr[i]通过增加一个条件判断只有当最小元素的索引不等于当前的第一个元素的索引时才进行交换操作。这样就可以减少不必要的交换进而优化选择排序的性能。这个优化对于已经近乎有序的数组尤为有效因为这些情况下交换次数较少。尽管选择排序的时间复杂度仍然是O(n^2)但这样的优化可以提高它的效率。
2.3 复杂度
时间复杂度最坏情况O(N^2) 最好情况O(N^2) 空间复杂度O(1)
三、插入排序
插入排序Insertion Sort是一种简单的排序算法其基本思想是将数组分为已排序和未排序两个部分逐个将未排序元素插入到已排序部分的适当位置使其保持有序。
在待排序的元素中假设前n-1个元素已有序现将第n个元素插入到前面已经排好的序列中使得前n个元素有序。按照此法对所有元素进行插入直到整个序列有序。 但我们并不能确定待排元素中究竟哪一部分是有序的所以我们一开始只能认为第一个元素是有序的依次将其后面的元素插入到这个有序序列中来直到整个序列有序为止。 案例
3.1 代码
def insertion_sort(arr):n len(arr)for i in range(1, n):key arr[i] # 当前要插入的元素j i - 1 # 已排序部分的最后一个元素的索引# 逐个将已排序部分中比key大的元素后移为key找到合适的插入位置while j 0 and key arr[j]:arr[j 1] arr[j]j - 1# 插入key到合适的位置arr[j 1] key在插入排序中外层循环控制需要插入的次数从第2个元素开始索引为1依次向已排序部分插入未排序部分的元素。内层循环用于将已排序部分中比当前元素key大的元素后移为key找到合适的插入位置。最后将key插入到合适的位置完成一次插入操作。
改进 在外层循环控制的插入次数所有的元素都要被插入因此无法提前截止。内层循环控制的是插入位置一一倒序比较插入的位置是否合适。为了更快的找到插入位置可以使用二分法判断插入位置。
3.2 优化的代码
def insertion_sort(arr):n len(arr)for i in range(1, n):key arr[i]left, right 0, i - 1# 使用二分查找找到key应该插入的位置while left right:mid (left right) // 2if arr[mid] key:right mid - 1else:left mid 1# 将已排序部分中大于key的元素都后移一位for j in range(i, left, -1):arr[j] arr[j - 1]arr[left] key# 使用示例
arr [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print(arr) # 输出[11, 12, 22, 25, 34, 64, 90]3.3 复杂度
时间复杂度 最坏情况下为O(N*N)此时待排序列为逆序或者说接近逆序 最好情况下为O(N)此时待排序列为升序或者说接近升序。 空间复杂度O(1)
四、快速排序
快速排序Quick Sort是一种高效的排序算法它使用分治法来对数组进行排序。快速排序的基本思想是选择一个基准元素pivot然后将数组中小于等于基准的元素放在左边大于基准的元素放在右边然后分别对左右两部分递归地进行快速排序直到整个数组有序为止。
案例 以【34,25,11,22,12,64,90】为例。 4.1 代码
def quick_sort(arr):if len(arr) 1:return arrpivot 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)改进 在优化快速排序的代码中主要关注减少递归调用的次数和减少额外空间的使用。以下是针对这两方面的优化方法
优化递归调用次数对于小规模的子数组可以切换到其他排序算法例如插入排序。这是因为在小规模数据下插入排序的常数项较小比快速排序的递归开销更小。减少额外空间的使用原始的快速排序需要额外的数组空间用于存放左右子数组但我们可以通过就地分区的方式来减少空间使用。
或者说是用挖坑法 减少额外空间的使用。注意在减少空间使用的的快速排序算法有很多下面这个动态图比较形象所以放在这里的。这与我们 下面使用的partition的代码不一致。 4.2 优化的代码
对于小规模的子数组切换到插入排序
def insertion_sort(arr, low, high):for i in range(low 1, high 1):key arr[i]j i - 1while j low and key arr[j]:arr[j 1] arr[j]j - 1arr[j 1] keydef partition(arr, low, high):pivot arr[high] ##注意这里的坑位与前面的动态图相反选择的是最后一个位置而不是首位置i low - 1for j in range(low, high):if arr[j] pivot:i 1arr[i], arr[j] arr[j], arr[i]arr[i 1], arr[high] arr[high], arr[i 1]return i 1def quick_sort(arr, low, high):if low high:# 对于小规模的子数组切换到插入排序if high - low 1 10:insertion_sort(arr, low, high)else:pivot_index partition(arr, low, high)quick_sort(arr, low, pivot_index - 1)quick_sort(arr, pivot_index 1, high)测试
arr [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # 输出[11, 12, 22, 25, 34, 64, 90]在优化后的代码中我们引入了insertion_sort函数用于对小规模子数组进行插入排序。当子数组大小不超过10个元素时切换到插入排序。同时在quick_sort函数中采用就地分区的方法减少了额外的空间使用。 这些优化方法可以提高快速排序在小规模数据和近乎有序数组的性能。但需要注意的是优化的效果也依赖于具体的数据情况
4.3 案例讲解–partition的应用
以【72,64,34,25,12,22,90,17,45,58】为例。当子数组规模小于3的时候切换到“插入排序”。以其中一轮为例。
递归调用的树状图
五、 归并算法
归并排序Merge Sort是一种高效稳定的排序算法它使用分治法将数组分为两个子数组递归地对子数组进行排序然后将排好序的子数组合并成一个有序数组。
5.1 代码
def merge_sort(arr):if len(arr) 1:return arr# 将数组一分为二mid len(arr) // 2left arr[:mid]right arr[mid:]# 递归对左右两部分进行归并排序left merge_sort(left)right merge_sort(right)# 合并已排序的左右两部分return merge(left, right)def merge(left, right):merged []left_idx, right_idx 0, 0while left_idx len(left) and right_idx len(right):if left[left_idx] right[right_idx]:merged.append(left[left_idx])left_idx 1else:merged.append(right[right_idx])right_idx 1# 将剩余的元素加入合并后的数组merged.extend(left[left_idx:])merged.extend(right[right_idx:])return merged
