排序算法 - 快速排序（4种方法实现）

**快速排序算法**

快速排序是一种常见的排序算法，属于分治类算法。它通过选择一个基准值，将数据集分成两个子集：小于基准值的元素和大于基准值的元素，然后递归地对这两个子集进行排序。

**快速排序的四种实现方法**

###1. **Lomuto 分割算法**

Lomuto 分割算法是快速排序中最常用的分割算法。它通过选择一个基准值，将数据集分成两个子集：小于基准值的元素和大于基准值的元素。

def lomuto_partition(arr, low, high):
 """
 Lomuto 分割算法 :param arr: 数据集 :param low: 左边界 :param high: 右边界 :return: 基准值索引 """
 pivot = arr[high] #选择基准值为最后一个元素 i = low -1 # 小于基准值的元素索引 for j in range(low, high):
 if arr[j] <= pivot:
 i +=1 arr[i], arr[j] = arr[j], arr[i]

 arr[i +1], arr[high] = arr[high], arr[i +1]
 return i +1def quicksort_lomuto(arr, low, high):
 """
 快速排序（Lomuto 分割算法）

 :param arr: 数据集 :param low: 左边界 :param high: 右边界 """
 if low < high:
 pivot_index = lomuto_partition(arr, low, high)
 quicksort_lomuto(arr, low, pivot_index -1) # 递归排序小于基准值的元素 quicksort_lomuto(arr, pivot_index +1, high) # 递归排序大于基准值的元素# 示例代码arr = [5,2,8,3,1,6,4]
quicksort_lomuto(arr,0, len(arr) -1)
print(arr) # 输出：[1,2,3,4,5,6,8]

def hoare_partition(arr, low, high):
 """
 Hoare 分割算法 :param arr: 数据集 :param low: 左边界 :param high: 右边界 :return: 基准值索引 """
 pivot1 = arr[low] # 第一个基准值 pivot2 = arr[high] # 第二个基准值 i = low -1 # 小于第一个基准值的元素索引 j = high +1 # 大于第二个基准值的元素索引 while True:
 i +=1 while arr[i] < pivot2: # 找到大于第二个基准值的元素 i +=1 j -=1 while arr[j] > pivot1: # 找到小于第一个基准值的元素 j -=1 if i >= j:
 break arr[i], arr[j] = arr[j], arr[i]

 arr[low], arr[j] = arr[j], arr[low]
 return jdef quicksort_hoare(arr, low, high):
 """
 快速排序（Hoare 分割算法）

 :param arr: 数据集 :param low: 左边界 :param high: 右边界 """
 if low < high:
 pivot_index = hoare_partition(arr, low, high)
 quicksort_hoare(arr, low, pivot_index) # 递归排序小于第一个基准值的元素 quicksort_hoare(arr, pivot_index +1, high) # 递归排序大于第二个基准值的元素# 示例代码arr = [5,2,8,3,1,6,4]
quicksort_hoare(arr,0, len(arr) -1)
print(arr) # 输出：[1,2,3,4,5,6,8]

def dual_quicksort(arr):
 """
 双向快速排序 :param arr: 数据集 """
 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 dual_quicksort(left) + middle + dual_quicksort(right)

# 示例代码arr = [5,2,8,3,1,6,4]
print(dual_quicksort(arr)) # 输出：[1,2,3,4,5,6,8]

def heapify(arr, n, i):
 """
 堆化 :param arr: 数据集 :param n: 堂数 :param 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 heapsort(arr):
 """
 堆排序 :param 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)

# 示例代码arr = [5,2,8,3,1,6,4]
heapsort(arr)
print(arr) # 输出：[1,2,3,4,5,6,8]