七大排序算法和计数排序

**七大排序算法与计数排序**

排序是计算机科学中一个非常重要的概念，它涉及到将数据按一定顺序排列。有很多种不同的排序算法，每种算法都有其特点和应用场景。在本文中，我们将介绍七大排序算法（冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和基数排序）以及计数排序。

###1. 冒泡排序冒泡排序是一种简单的排序算法，它通过反复地遍历列表，相邻元素之间进行比较和交换，以达到排序的目的。冒泡排序的时间复杂度为 O(n^2)，其中 n 是列表中的元素个数。

def bubble_sort(arr):
 """
 冒泡排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 n = len(arr)
 for i in range(n-1):
 # 每轮比较两两相邻元素 for j in range(n-i-1):
 if arr[j] > arr[j+1]:
 # 如果前者大于后者，则交换它们 arr[j], arr[j+1] = arr[j+1], arr[j]
 return arr# 示例使用arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", bubble_sort(arr))

###2.选择排序选择排序是一种简单的排序算法，它通过在每一轮中找出最小或最大元素，并将其放在对应位置，以达到排序的目的。选择排序的时间复杂度为 O(n^2)。

def selection_sort(arr):
 """
选择排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 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]
 return arr# 示例使用arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", selection_sort(arr))

###3. 插入排序插入排序是一种简单的排序算法，它通过将每个元素插入到已经排好序的列表中，以达到排序的目的。插入排序的时间复杂度为 O(n^2)。

def insertion_sort(arr):
 """
 插入排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 j = i-1 # 将元素插入到已经排好序的列表中 while j >=0 and arr[j] > key:
 arr[j+1] = arr[j]
 j -=1 arr[j+1] = key return arr# 示例使用arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", insertion_sort(arr))

###4. 归并排序归并排序是一种分治法的排序算法，它通过将列表分成两半，然后分别对每半进行排序，并将它们合并起来，以达到排序的目的。归并排序的时间复杂度为 O(n log n)。

def merge_sort(arr):
 """
 归并排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 if len(arr) <=1:
 return arr mid = len(arr) //2 left = merge_sort(arr[:mid])
 right = merge_sort(arr[mid:])
 return merge(left, right)

def merge(left, right):
 result = []
 while left and right:
 if left[0] < right[0]:
 result.append(left.pop(0))
 else:
 result.append(right.pop(0))
 result.extend(left)
 result.extend(right)
 return result# 示例使用arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", merge_sort(arr))

###5. 快速排序快速排序是一种分治法的排序算法，它通过选择一个元素作为基准点，然后将其他元素分成两半，分别小于或大于该基准点，以达到排序的目的。快速排序的时间复杂度为 O(n log n)。

def quick_sort(arr):
 """
 快速排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 if len(arr) <=1:
 return arr pivot = 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 = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", quick_sort(arr))

###6. 堆排序堆排序是一种分治法的排序算法，它通过将列表建成一个最大堆，然后逐步地从堆中取出元素，并将其放在对应位置，以达到排序的目的。堆排序的时间复杂度为 O(n log n)。

def heapify(arr, n, i):
 largest = i left =2 * i +1 right =2 * i +2 if left < n and arr[left] > arr[largest]:
 largest = left if right < n and arr[right] > arr[largest]:
 largest = right if largest != i:
 arr[i], arr[largest] = arr[largest], arr[i]
 heapify(arr, n, largest)

def heap_sort(arr):
 """
 堆排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 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[0], arr[i] = arr[i], arr[0]
 heapify(arr, i,0)
 return arr# 示例使用arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", heap_sort(arr))

###7. 基数排序基数排序是一种稳定的排序算法，它通过将数字按一定的基数进行分类，然后对每个桶中的元素进行排序，以达到排序的目的。基数排序的时间复杂度为 O(nk)，其中 n 是列表中的元素个数，k 是基数。

def radix_sort(arr):
 """
 基数排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 RADIX =10 max_length = False tmp, placement = -1,0 while not max_length:
 max_length = True # 统计每个桶中的元素个数 buckets = [list() for _ in range(RADIX)]
 for i in arr:
 tmp = i // (RADIX ** placement)
 buckets[tmp % RADIX].append(i)
 if max_length and tmp >0:
 max_length = False a =0 # 将元素放回原列表中 for b in range(RADIX):
 buck = buckets[b]
 for i in buck:
 arr[a] = i a +=1 placement +=1 return arr# 示例使用arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", radix_sort(arr))