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

目录该算法主要包含三个步骤选择枢轴点分区算法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.hvoid swap(int* a, int* b);// partition functionint partition(int arr[], int low, int high) {// Choose the pivotint pivot arr[high];// Index of smaller element and indicates// the right position of pivot found so farint 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 iterationfor (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 positionswap(arr[i 1], arr[high]);return i 1;}// The QuickSort function implementationvoid quickSort(int arr[], int low, int high) {if (low high) {// pi is the partition return index of pivotint pi partition(arr, low, high);// recursion calls for smaller elements// and greater or equals elementsquickSort(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;}输出1 5 7 8 9 10快速排序算法的复杂度分析时间复杂度最佳情况(Ω(n log n))当枢轴元素将数组分成两个相等的部分时发生。平均情况(θ(n log n))平均而言枢轴将数组分成两部分但不一定相等。最坏情况(O(n²))当总是选择最小或最大的元素作为枢轴时发生例如已排序的数组。辅助空间最坏情况由于不平衡的分区导致递归树倾斜需要大小为 O(n ) 的调用栈因此复杂度为 O(n)。最佳情况由于均衡划分得到一个均衡的递归树其调用栈大小为 O(log n)因此时间复杂度为 O(log n)。更多详情请参阅快速排序的时间和空间复杂度分析。快速排序的优势它是一种分治算法可以更轻松地解决问题。它处理大型数据集非常高效。它占用资源少运行只需要少量内存。由于我们对同一个数组进行排序并且不会将数据复制到任何辅助数组因此它对缓存友好。当对稳定性要求不高时适用于大数据处理的最快通用算法。它是尾递归的因此可以进行所有尾调用优化。快速排序的缺点它的最坏情况时间复杂度为 O(n 2 )这种情况发生在枢轴选择不当时。对于小型数据集来说这不是一个好的选择。它不是稳定排序这意味着如果两个元素具有相同的键则在快速排序的情况下它们的相对顺序不会在排序后的输出中保留因为在这里我们根据枢轴的位置交换元素而不考虑它们的原始位置。快速排序的应用在内存中高效地对大型数据集进行排序。用于库排序函数如 C std::sort 和 Java Arrays.sort 用于基本数据类型。对数据库中的记录进行排序以便更快地进行搜索。需要排序输入的算法的预处理步骤例如二分查找、双指针技术。使用快速选择快速排序的一种变体查找第 k 个最小/最大的元素。根据多个键自定义比较器对对象数组进行排序。数据压缩算法如霍夫曼编码预处理。图形学和计算几何例如凸包算法。更多详情请参阅快速排序的应用。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。