【数据结构与算法】归并排序，计数排序，快速排序，堆排序

**数据结构与算法**

在计算机科学中，数据结构和算法是两个基本概念，它们共同构成了计算机程序的核心。数据结构是指组织和存储数据的方式，而算法则是指解决问题或完成任务的一系列步骤。在本文中，我们将讨论四种常见的排序算法：归并排序、计数排序、快速排序和堆排序。

###1. 归并排序归并排序是一种分治法，通过递归地将数组分成两个子数组，然后对每个子数组进行排序，最终合并两个有序子数组得到最终的有序数组。归并排序的时间复杂度为 O(n log n)，其中 n 是数组长度。

####代码示例

def merge_sort(arr):
 # 如果数组长度小于或等于1，则返回原数组（因为已经是有序的）
 if len(arr) <=1:
 return arr # 将数组分成两个子数组 mid = len(arr) //2 left = arr[:mid]
 right = arr[mid:]
 # 递归地对每个子数组进行排序 left = merge_sort(left)
 right = merge_sort(right)
 # 合并两个有序子数组得到最终的有序数组 return merge(left, right)

def merge(left, right):
 result = []
 while len(left) >0 and len(right) >0:
 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))

def count_sort(arr):
 # 找到最大值和最小值 min_val = min(arr)
 max_val = max(arr)
 # 计算范围 range_val = max_val - min_val +1 # 创建计数数组 count_arr = [0] * range_val # 对每个元素进行计数 for num in arr:
 count_arr[num - min_val] +=1 # 构造有序数组 sorted_arr = []
 for i in range(range_val):
 sorted_arr.extend([i + min_val] * count_arr[i])
 return sorted_arr# 测试arr = [4,2,2,8,3,3,1]
print("原始数组：", arr)
print("排序后数组：", count_sort(arr))

def quick_sort(arr):
 # 如果数组长度小于或等于1，则返回原数组（因为已经是有序的）
 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))

def heapify(arr, n, i):
 largest = i left =2 * i +1 right =2 * i +2 if left < n and arr[i] < arr[left]:
 largest = left if right < n and arr[largest] < arr[right]:
 largest = right if 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[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))