当前位置：首页 > news >正文

C语言基于分治法的快速排序算法(Quick Sort)

news 2026/6/24 5:53:27

该算法主要包含三个步骤

选择枢轴点

分区算法

Lomuto分割算法的工作原理及图示

快速排序算法示意图

快速排序算法的复杂度分析

快速排序的优势

快速排序的缺点

快速排序的应用

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

快速排序是一种基于分治法的排序算法，它选择一个元素作为枢轴，并将给定数组围绕该枢轴进行划分，最终将枢轴放置在排序数组中的正确位置。

该算法主要包含三个步骤

选择枢轴元素：从数组中选择一个元素作为枢轴元素。枢轴元素的选择可以是多种多样的（例如，第一个元素、最后一个元素、随机元素或中位数）。

对数组进行分区：围绕中心元素重新排列数组。分区后，所有小于中心元素的元素都将位于中心元素的左侧，所有大于中心元素的元素都将位于中心元素的右侧。

递归调用：递归地对两个分区子数组应用相同的过程。

基本情况：当子数组中只剩下一个元素时，递归停止，因为单个元素已经排序。

选择枢轴点

选择枢轴点有很多不同的方法。

始终选择第一个（或最后一个）元素作为枢轴。下面的实现选择最后一个元素作为枢轴。这种方法的缺点是，当数组已经排序时，最终结果会非常糟糕。
随机选择一个元素作为枢轴点。这种方法更可取，因为它不存在导致最坏情况发生的固定模式。
选择中位数作为枢轴元素。就时间复杂度而言，这是一种理想的方法，因为我们可以在线性时间内找到中位数，并且配分函数总是会将输入数组分成两半。但由于中位数查找的常数较大，因此平均耗时更长。

分区算法

快速排序的关键步骤是分区（partition()）。分区有三种常用的算法。所有这些算法的时间复杂度都是 O(n)。

朴素分区：这里我们创建数组的副本。首先放入所有较小的元素，然后放入所有较大的元素。最后将临时数组复制回原始数组。这需要 O(n) 的额外空间。
Lomuto分区：本文使用了这种分区方法。这是一个简单的算法，它跟踪较小元素的索引并不断交换索引。之所以选择它，是因为它简单易用。
霍尔分割法：这是所有分割方法中最快的。它从数组的两侧遍历，不断将左侧较大的元素与右侧较小的元素交换，但数组本身并未被分割。详情请参阅霍尔分割法与洛穆托分割法的比较。

以上红色部分参考链接：

以第一个元素为枢轴元素实现快速排序
C++ C++ (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序_c++ pivot-CSDN博客
C语言 C语言 (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
Java Java (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
Python Python (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
C# C# (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
JavaScript JavaScript (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客

使用随机枢轴的快速排序
C++ C++ (QuickSort using Random Pivoting)使用随机枢轴的快速排序_霍尔分区-CSDN博客
C语言 C语言 (QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
Java Java(QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
Python Python (QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
C# C# (QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
JavaScript JavaScript (QuickSort using Random Pivoting)使用随机枢轴的快速排序_quick pivot(快速枢轴)插件-CSDN博客

数组的中位数
C++ C++ (Median of an Array)数组的中位数_c++如何查找数组中间元素-CSDN博客
Java Java (Median of an Array)数组的中位数-CSDN博客
Python Python (Median of an Array)数组的中位数-CSDN博客
C# C# (Median of an Array)数组的中位数_c#求数组中值-CSDN博客
JavaScript JavaScript (Median of an Array)数组的中位数_js 计算数组中位数-CSDN博客

朴素划分算法
C++ C++ (Naive Partition Algorithm)朴素划分算法-CSDN博客
C语言 C语言 (Naive Partition Algorithm)朴素划分算法-CSDN博客
Java Java (Naive Partition Algorithm)朴素划分算法-CSDN博客
Python Python (Naive Partition Algorithm)朴素划分算法-CSDN博客
C# C# (Naive Partition Algorithm)朴素划分算法-CSDN博客
JavaScript JavaScript (Naive Partition Algorithm)朴素划分算法-CSDN博客

Lomuto分区算法
C++ C++ Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
C语言 C语言 Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
Java Java Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
Python Python Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
C# C# Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
JavaScript JavaScript Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客

霍尔分区算法
C++ C++ 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
C语言 C语言霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
Java Java 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
Python Python 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
C# C# 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
JavaScript JavaScript 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客

Lomuto分割算法的工作原理及图示

逻辑很简单，我们从最左边的元素开始，并将小于（或等于）当前元素的索引记为i。遍历过程中，如果找到更小的元素，则将当前元素与arr[i]交换。否则，忽略当前元素。

让我们借助以下示例来理解分区算法的工作原理：

快速排序算法示意图

在上一步中，我们了解了分区过程如何根据选定的枢轴元素重新排列数组。接下来，我们将相同的方法递归应用于枢轴元素左右两侧的较小子数组。每次，我们都选择新的枢轴元素并再次分区数组。此过程持续进行，直到只剩下一个元素为止，该元素始终是有序的。一旦每个元素都位于其正确的位置，整个数组就排序完成了。

下图展示了递归方法如何调用枢轴元素左右两侧的较小子数组：

示例代码：

#include <stdio.h>

void swap(int* a, int* b);

// partition function
int partition(int arr[], int low, int high) {

// Choose the pivot
int pivot = arr[high];

// Index of smaller element and indicates
// the right position of pivot found so far
int i = low - 1;

// Traverse arr[low..high] and move all smaller
// elements to the left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}

// Move pivot after smaller elements and
// return its position
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

// The QuickSort function implementation
void quickSort(int arr[], int low, int high) {
if (low < high) {

// pi is the partition return index of pivot
int pi = partition(arr, low, high);

// recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

输出