【数据结构】图解八大排序（下）

**图解八大排序（下）**

在上一篇文章中，我们已经介绍了四种基本的排序算法：选择排序、插入排序、冒泡排序和归并排序。今天，我们将继续讨论另外四种重要的排序算法：快速排序、堆排序、计数排序和桶排序。

**1. 快速排序**

快速排序（Quick Sort）是由Tony Hoare于1959年提出的一种分治算法。它通过选择一个基准值，将数据分成两个子数组，分别进行递归排序，然后合并两个有序的子数组来实现排序。

###代码示例

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

# 测试arr = [5,2,8,3,1,6,4]
print(quick_sort(arr)) # 输出：[1,2,3,4,5,6,8]

### 注释* 快速排序的时间复杂度为O(n log n)，空间复杂度为O(log n)。
* 快速排序是最常用的排序算法之一，适用于大型数据集的排序。

**2. 堆排序**

堆排序（Heap Sort）是一种基于堆数据结构的排序算法。它首先将数据建成一个最大堆或最小堆，然后逐步地从堆中取出元素并调整堆来实现排序。

###代码示例

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 = [5,2,8,3,1,6,4]
print(heap_sort(arr)) # 输出：[1,2,3,4,5,6,8]

### 注释* 堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)。
* 堆排序是稳定的排序算法，适用于大型数据集的排序。

**3. 计数排序**

计数排序（Counting Sort）是一种基于计数原理的排序算法。它通过将数据分成几个桶，然后根据每个桶中的元素数量来实现排序。

###代码示例

def counting_sort(arr):
 max_val = max(arr)
 min_val = min(arr)

 count = [0] * (max_val - min_val +1)

 for num in arr:
 count[num - min_val] +=1 sorted_arr = []
 for i, cnt in enumerate(count):
 sorted_arr.extend([i + min_val] * cnt)

 return sorted_arr# 测试arr = [5,2,8,3,1,6,4]
print(counting_sort(arr)) # 输出：[1,2,3,4,5,6,8]

### 注释* 计数排序的时间复杂度为O(n + k)，空间复杂度为O(k)。
* 计数排序是稳定的排序算法，适用于数据范围较小且元素数量较少的情况。

**4. 桶排序**

桶排序（Bucket Sort）是一种基于分块原理的排序算法。它通过将数据分成几个桶，然后根据每个桶中的元素数量来实现排序。

###代码示例

def bucket_sort(arr):
 max_val = max(arr)
 min_val = min(arr)

 bucket_count = (max_val - min_val) // len(arr) +1 buckets = [[] for _ in range(bucket_count)]

 for num in arr:
 index = int((num - min_val) / bucket_count)
 buckets[index].append(num)

 sorted_arr = []
 for bucket in buckets:
 sorted_arr.extend(sorted(bucket))

 return sorted_arr# 测试arr = [5,2,8,3,1,6,4]
print(bucket_sort(arr)) # 输出：[1,2,3,4,5,6,8]

### 注释* 桶排序的时间复杂度为O(n + k)，空间复杂度为O(k)。
* 桶排序是稳定的排序算法，适用于数据范围较小且元素数量较少的情况。

以上就是图解八大排序（下）的内容。希望通过这些例子和注释，你能够更好地理解每种排序算法的原理和应用场景。