国外设计公司网站,wordpress电影主题网站,下载手机app软件,国外网站建设的研究现状各种常见排序算法总结
一. 冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表#xff0c;比较相邻的元素#xff0c;并交换它们的位置#xff0c;直到整个列表排序完成。
A、说明#xff1a;
特点#xff1a;
通过不断交换相邻元素比较相邻的元素并交换它们的位置直到整个列表排序完成。
A、说明
特点
通过不断交换相邻元素将最大或最小的元素“冒泡”到数组的一端。
优点
实现简单代码容易理解。对于小规模数据表现较好。
缺点
时间复杂度较高不适合大规模数据。交换操作较多效率低。
时间复杂度
最好情况O(n)已经有序最坏情况O(n²)平均情况O(n²)
空间复杂度
O(1)原地排序
稳定性
稳定
B、步骤 从列表的第一个元素开始比较相邻的两个元素。 如果前一个元素比后一个元素大交换它们的位置。 继续遍历列表直到没有需要交换的元素。
C、示例代码
def bubble_sort(arr):n len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] arr[j1]:arr[j], arr[j1] arr[j1], arr[j]return arr# 示例
arr [64, 34, 25, 12, 22, 11, 90]
print(排序前:, arr)
print(排序后:, bubble_sort(arr))二、选择排序 (Selection Sort)
选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中选择最小或最大的元素放到已排序部分的末尾。
A、说明
特点
每次从未排序部分选择最小或最大的元素放到已排序部分的末尾。
优点
实现简单。不占用额外空间。
缺点
时间复杂度较高不适合大规模数据。不稳定可能改变相同元素的相对顺序。
时间复杂度
最好情况O(n²)最坏情况O(n²)平均情况O(n²)
空间复杂度
O(1)原地排序
稳定性
不稳定
B、步骤 在未排序部分中找到最小元素。 将最小元素与未排序部分的第一个元素交换。 重复上述步骤直到所有元素排序完成。
C、示例代码
def selection_sort(arr):n len(arr)for i in range(n):min_idx ifor j in range(i1, n):if arr[j] arr[min_idx]:min_idx jarr[i], arr[min_idx] arr[min_idx], arr[i]return arr# 示例
arr [64, 25, 12, 22, 11]
print(排序前:, arr)
print(排序后:, selection_sort(arr))三、插入排序 (Insertion Sort)
插入排序是一种简单直观的排序算法。它的工作原理是将未排序部分的元素逐个插入到已排序部分的适当位置。
A、说明
特点
将未排序部分的元素逐个插入到已排序部分的正确位置。
优点
对于小规模或基本有序的数据效率较高。实现简单。
缺点
时间复杂度较高不适合大规模数据。数据移动较多。
时间复杂度
最好情况O(n)已经有序最坏情况O(n²)平均情况O(n²)
空间复杂度
O(1)原地排序
稳定性
稳定
B、步骤 从第一个元素开始该元素可以认为已经被排序。 取出下一个元素在已经排序的元素序列中从后向前扫描。 如果该元素已排序大于新元素将该元素移到下一位置。 重复步骤3直到找到已排序的元素小于或等于新元素的位置。 将新元素插入到该位置后。 重复步骤2~5。
C、示例代码
def insertion_sort(arr):for i in range(1, len(arr)):key arr[i]j i-1while j 0 and key arr[j]:arr[j1] arr[j]j - 1arr[j1] keyreturn arr# 示例
arr [12, 11, 13, 5, 6]
print(排序前:, arr)
print(排序后:, insertion_sort(arr))四、快速排序 (Quick Sort)
快速排序是一种高效的排序算法采用分治法策略。它通过选择一个“基准”元素将数组分为两部分一部分比基准小另一部分比基准大然后递归地对这两部分进行排序。
A、说明
特点
采用分治法选择一个基准元素将数组分为两部分左边小于基准右边大于基准然后递归排序。
优点
平均情况下效率非常高。适合大规模数据。
缺点
最坏情况下时间复杂度较高O(n²)。不稳定。
时间复杂度
最好情况O(n log n)最坏情况O(n²)当数组已经有序时平均情况O(n log n)
空间复杂度
O(log n)递归栈空间
稳定性
不稳定
B、步骤 选择一个基准元素。 将数组分为两部分一部分比基准小另一部分比基准大。 递归地对这两部分进行快速排序。
C、示例代码
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)# 示例
arr [10, 7, 8, 9, 1, 5]
print(排序前:, arr)
print(排序后:, quick_sort(arr))五、归并排序 (Merge Sort)
归并排序是一种稳定的排序算法采用分治法策略。它将数组分成两半分别对它们进行排序然后将排序后的两半合并。
A、说明
特点
采用分治法将数组分成两部分分别排序后合并。
优点
时间复杂度稳定适合大规模数据。稳定排序。
缺点
需要额外的存储空间。对于小规模数据效率不如插入排序。
时间复杂度
最好情况O(n log n)最坏情况O(n log n)平均情况O(n log n)
空间复杂度
O(n)需要额外的数组空间
稳定性
稳定
B、步骤 将数组分成两半。 递归地对每一半进行归并排序。 将排序后的两半合并。
C、示例代码
def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid])right merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result []i j 0while i len(left) and j len(right):if left[i] right[j]:result.append(left[i])i 1else:result.append(right[j])j 1result.extend(left[i:])result.extend(right[j:])return result# 示例
arr [38, 27, 43, 3, 9, 82, 10]
print(排序前:, arr)
print(排序后:, merge_sort(arr))六、堆排序 (Heap Sort)
堆排序是一种基于二叉堆的排序算法。它首先将数组构建成一个最大堆然后逐步将堆顶元素最大值与堆的最后一个元素交换并调整堆直到整个数组排序完成。
A、说明
特点
利用堆数据结构将数组构建成最大堆或最小堆然后逐个取出堆顶元素。
优点
时间复杂度稳定适合大规模数据。不占用额外空间原地排序。
缺点
不稳定。实现较复杂。
时间复杂度
最好情况O(n log n)最坏情况O(n log n)平均情况O(n log n)
空间复杂度
O(1)原地排序
稳定性
不稳定
B、步骤 构建一个最大堆。 将堆顶元素最大值与堆的最后一个元素交换。 调整堆使其重新成为最大堆。 重复步骤2~3直到堆的大小为1。
C、示例代码
def heapify(arr, n, i):largest ileft 2 * i 1right 2 * i 2if left n and arr[i] arr[left]:largest leftif right n and arr[largest] arr[right]:largest rightif largest ! i:arr[i], arr[largest] arr[largest], arr[i]heapify(arr, n, largest)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# 示例
arr [12, 11, 13, 5, 6, 7]
print(排序前:, arr)
print(排序后:, heap_sort(arr))七、希尔排序 (Shell Sort)
希尔排序是插入排序的一种高效改进版本。它通过将数组分成若干个子序列分别进行插入排序然后逐步缩小子序列的间隔最终完成排序。
A、说明
特点
是插入排序的改进版通过分组插入排序逐步缩小分组间隔。
优点
对于中等规模数据效率较高。比插入排序更快。
缺点
时间复杂度依赖于增量序列的选择。不稳定。
时间复杂度
最好情况O(n log n)最坏情况O(n²)平均情况取决于增量序列
空间复杂度
O(1)原地排序
稳定性
不稳定
B、步骤 选择一个增量序列例如n/2, n/4, …, 1。 对每个增量进行插入排序。 逐步缩小增量直到增量为1。
C、示例代码
def shell_sort(arr):n len(arr)gap n // 2while gap 0:for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempgap // 2return arr# 示例
arr [12, 34, 54, 2, 3]
print(排序前:, arr)
print(排序后:, shell_sort(arr))八、计数排序 (Counting Sort)
计数排序是一种非比较排序算法适用于整数排序。它通过统计每个元素的出现次数然后根据统计结果将元素放回正确的位置。
A、说明
特点
适用于整数排序通过统计每个元素的出现次数然后依次输出。
优点
时间复杂度低适合数据范围较小的整数排序。
缺点
需要额外的存储空间。只适用于整数排序。
时间复杂度
最好情况O(n k)k是数据范围最坏情况O(n k)平均情况O(n k)
空间复杂度
O(k)需要额外的计数数组
稳定性
稳定
B、步骤 统计每个元素的出现次数。 计算每个元素在排序后数组中的位置。 将元素放回正确的位置。
C、示例代码
def counting_sort(arr):max_val max(arr)count [0] * (max_val 1)for num in arr:count[num] 1sorted_arr []for i in range(len(count)):sorted_arr.extend([i] * count[i])return sorted_arr# 示例
arr [4, 2, 2, 8, 3, 3, 1]
print(排序前:, arr)
print(排序后:, counting_sort(arr))九、桶排序 (Bucket Sort)
桶排序是一种分布式排序算法它将元素分到若干个桶中每个桶分别进行排序最后将桶中的元素合并。
A、说明
特点
将数据分到多个桶中每个桶单独排序最后合并。
优点
适合数据分布均匀的情况。时间复杂度较低。
缺点
需要额外的存储空间。数据分布不均匀时效率下降。
时间复杂度
最好情况O(n k)k是桶的数量最坏情况O(n²)平均情况O(n k)
空间复杂度
O(n k)需要额外的桶空间
稳定性
稳定
B、步骤 将元素分到若干个桶中。 对每个桶中的元素进行排序。 将桶中的元素合并。
C、示例代码
def bucket_sort(arr):max_val max(arr)min_val min(arr)bucket_range (max_val - min_val) / len(arr)buckets [[] for _ in range(len(arr))]for num in arr:index int((num - min_val) // bucket_range)if index ! len(arr):buckets[index].append(num)else:buckets[-1].append(num)sorted_arr []for bucket in buckets:sorted_arr.extend(sorted(bucket))return sorted_arr# 示例
arr [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
print(排序前:, arr)
print(排序后:, bucket_sort(arr))十、基数排序 (Radix Sort)
基数排序是一种非比较排序算法它通过将整数按位数切割成不同的数字然后按每个位数分别进行排序。
A、说明
特点
按照位数从低到高或从高到低依次排序。
优点
适合整数或字符串排序。时间复杂度较低。
缺点
需要额外的存储空间。只适用于整数或字符串排序。
时间复杂度
最好情况O(n × k)k是最大位数最坏情况O(n × k)平均情况O(n × k)
空间复杂度
O(n k)需要额外的桶空间
稳定性
稳定
B、步骤 找到数组中的最大数确定最大位数。 从最低位开始对数组进行计数排序。 重复步骤2直到最高位。
C、示例代码
def counting_sort_for_radix(arr, exp):n len(arr)output [0] * ncount [0] * 10for i in range(n):index arr[i] // expcount[index % 10] 1for i in range(1, 10):count[i] count[i - 1]i n - 1while i 0:index arr[i] // expoutput[count[index % 10] - 1] arr[i]count[index % 10] - 1i - 1for i in range(n):arr[i] output[i]def radix_sort(arr):max_val max(arr)exp 1while max_val // exp 0:counting_sort_for_radix(arr, exp)exp * 10return arr# 示例
arr [170, 45, 75, 90, 802, 24, 2, 66]
print(排序前:, arr)
print(排序后:, radix_sort(arr))十一、总结对比
排序算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性优点缺点适用场景冒泡排序(O(n))(O(n^2))(O(n^2))(O(1))稳定实现简单适合小规模数据效率低不适合大规模数据小规模数据选择排序(O(n^2))(O(n^2))(O(n^2))(O(1))不稳定实现简单不占用额外空间效率低不适合大规模数据小规模数据插入排序(O(n))(O(n^2))(O(n^2))(O(1))稳定对小规模数据或基本有序数据效率高效率低不适合大规模数据小规模或基本有序数据快速排序(O(n \log n))(O(n^2))(O(n \log n))(O(\log n))不稳定平均情况下效率高适合大规模数据最坏情况下效率低如数据已经有序大规模数据归并排序(O(n \log n))(O(n \log n))(O(n \log n))(O(n))稳定时间复杂度稳定适合大规模数据需要额外空间对小规模数据效率不如插入排序大规模数据堆排序(O(n \log n))(O(n \log n))(O(n \log n))(O(1))不稳定时间复杂度稳定适合大规模数据实现较复杂不稳定大规模数据希尔排序(O(n \log n))(O(n^2))(O(n \log n))(O(1))不稳定对小规模数据效率较高比插入排序更快时间复杂度依赖于增量序列的选择中等规模数据计数排序(O(n k))(O(n k))(O(n k))(O(n k))稳定时间复杂度低适合数据范围较小的整数排序需要额外空间仅适用于整数数据范围较小的整数排序桶排序(O(n k))(O(n^2))(O(n k))(O(n k))稳定适合数据分布均匀的情况需要额外空间对数据分布不均匀的情况效率低数据分布均匀的情况基数排序(O(n \times k))(O(n \times k))(O(n \times k))(O(n k))稳定适合整数排序尤其是位数较少的情况需要额外空间仅适用于整数整数或字符串排序
© 著作权归作者所有
