企业网站现状分析,租赁公司租赁业务,十大电子商务网站,如何自己网站接装修生意做排序算法概述
排序算法是计算机科学中的一个重要主题#xff0c;用于将一组数据按特定顺序排列。排序算法有很多种#xff0c;每种算法在不同情况下有不同的性能表现。不同的排序算法适用于不同的场景和数据特征。在选择排序算法时#xff0c;需要考虑数据规模、数据分布以…排序算法概述
排序算法是计算机科学中的一个重要主题用于将一组数据按特定顺序排列。排序算法有很多种每种算法在不同情况下有不同的性能表现。不同的排序算法适用于不同的场景和数据特征。在选择排序算法时需要考虑数据规模、数据分布以及性能要求。了解各种排序算法的原理和实现方法有助于在实际应用中选择最合适的排序方法。 以下是一些常见的排序算法
1.冒泡排序Bubble Sort
原理反复遍历要排序的列表每次比较相邻的两个元素如果顺序错误就交换直到没有需要交换的元素为止。 时间复杂度最坏和平均情况下都是 (2) 空间复杂度O(1)
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
2.选择排序Selection Sort
原理每次从未排序部分选择最小的元素放到已排序部分的末尾。 时间复杂度最坏和平均情况下都是 (2) 空间复杂度(1)
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 arr3.插入排序Insertion Sort
原理构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。 时间复杂度最坏和平均情况下都是 (2)最佳情况已排序是 () 空间复杂度(1)
def insertion_sort(arr):for i in range(1, len(arr)):key arr[i]j i-1while j 0 and key arr[j]:arr[j 1] arr[j]j - 1arr[j 1] keyreturn arr4.归并排序Merge Sort
原理采用分治法将数组分成两个子数组分别排序后合并。
时间复杂度最坏和平均情况下都是 (log) 空间复杂度O(n)
def merge_sort(arr):if len(arr) 1:mid len(arr) // 2L arr[:mid]R arr[mid:]merge_sort(L)merge_sort(R)i j k 0while i len(L) and j len(R):if L[i] R[j]:arr[k] L[i]i 1else:arr[k] R[j]j 1k 1while i len(L):arr[k] L[i]i 1k 1while j len(R):arr[k] R[j]j 1k 1return arr5.快速排序Quick Sort
原理采用分治法选择一个基准元素将数组分成两部分一部分比基准小一部分比基准大然后递归排序两部分。 时间复杂度最坏情况下是 O(n2)平均情况下是 O(nlogn)。 空间复杂度O(logn)递归调用栈
def partition(arr, low, high):pivot arr[high]i low - 1for j in range(low, high):if arr[j] pivot:i 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:pi partition(arr, low, high)quick_sort(arr, low, pi - 1)quick_sort(arr, pi 1, high)return arr
6. 希尔排序Shell Sort
原理改进版的插入排序通过将数据按一定间隔分组对每组进行插入排序然后逐渐减少间隔进行多次排序。
时间复杂度最坏情况下是 O(n2)但通常比插入排序快得多。 空间复杂度O(1)
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 arr7. 堆排序Heap Sort
原理利用堆这种数据结构来排序首先将数组构建成最大堆然后将堆顶元素最大值与末尾元素交换再对剩余元素进行堆调整重复此过程。 时间复杂度最坏和平均情况下都是O(nlogn) 空间复杂度O(1)
def heapify(arr, n, i):largest il 2 * i 1r 2 * i 2if l n and arr[i] arr[l]:largest lif r n and arr[largest] arr[r]:largest rif 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
8. 计数排序Counting Sort
原理适用于整数排序通过计数数组记录每个整数的出现次数然后按照顺序输出。 时间复杂度O(nk)其中 是数列中的最大值 空间复杂度O(k)
def counting_sort(arr):max_val max(arr)m max_val 1count [0] * m for a in arr:count[a] 1 i 0for a in range(m): for c in range(count[a]): arr[i] ai 1return arr
9. 桶排序Bucket Sort
原理将数组分成若干个桶每个桶内的元素分别进行排序然后合并所有桶内的元素得到有序序列。 时间复杂度最坏情况下是 O(n2)但通常情况下是 O(nk) 空间复杂度O(nk)
def bucket_sort(arr):bucket []slot_num 10 for i in range(slot_num):bucket.append([])for j in arr:index_b int(slot_num * j)bucket[index_b].append(j)for i in range(slot_num):bucket[i] insertion_sort(bucket[i])k 0for i in range(slot_num):for j in range(len(bucket[i])):arr[k] bucket[i][j]k 1return arr
10. 基数排序Radix Sort
原理按照个位、十位、百位等进行多次排序每次排序使用稳定的排序算法如计数排序。 时间复杂度 O(nk)其中k 是数的位数。 空间复杂度O(nk)
def counting_sort_for_radix(arr, exp1):n len(arr)output [0] * n count [0] * 10for i in range(0, n):index arr[i] // exp1count[index % 10] 1for i in range(1, 10):count[i] count[i - 1]i n - 1while i 0:index arr[i] // exp1output[count[index % 10] - 1] arr[i]count[index % 10] - 1i - 1for i in range(0, len(arr)):arr[i] output[i]def radix_sort(arr):max1 max(arr)exp 1while max1 / exp 1:counting_sort_for_radix(arr, exp)exp * 10return arr调用测试
arr [1,4,3,0,2]
print(f冒泡排序{bubble_sort(arr)})
print(f选择排序{selection_sort(arr)})
print(f插入排序{insertion_sort(arr)})
print(f归并排序{merge_sort(arr)})
print(f快速排序{quick_sort(arr,0,4)})
print(f希尔排序{shell_sort(arr)})
print(f堆排序 {heap_sort(arr)})
print(f计数排序{counting_sort(arr)})
print(f桶排序{bucket_sort([num/10 for num in arr])})
print(f基数排序{radix_sort(arr)})冒泡排序[0, 1, 2, 3, 4] 选择排序[0, 1, 2, 3, 4] 插入排序[0, 1, 2, 3, 4] 归并排序[0, 1, 2, 3, 4] 快速排序[0, 1, 2, 3, 4] 希尔排序[0, 1, 2, 3, 4] 堆排序 [0, 1, 2, 3, 4] 计数排序[0, 1, 2, 3, 4] 桶排序[0.0, 0.1, 0.2, 0.3, 0.4] 基数排序[0, 1, 2, 3, 4]
