网站导航
> 文章列表 > 快速排序，分治法实际应用（含码源与解析）

快速排序，分治法实际应用（含码源与解析）

网友: 文章列表 2024-03-21 16:37:10

快速排序，分治法实际应用（含码源与解析）

 🎊【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用✨，经典算法的解析✨都在这儿，欢迎大家前往订阅本专题，获取更多详细信息哦🎏🎏🎏

🪔本系列专栏 -  数据结构与算法_勾栏听曲_0

🍻欢迎大家  🏹  点赞👍  评论📨  收藏⭐️

📌个人主页 - 勾栏听曲_0的博客📝

🔑希望本文能对你有所帮助，如有不足请指正，共同进步吧🏆

🎇莫将画竹论难易，刚道繁难简更难。君看萧萧只数叶，满堂春风不胜寒。📈

定义

        快速排序是另一种基于分治技术的重要排序算法。与我们上一篇所讲的合并排序不一样。合并排序是按照元素在数组中的位置对它们进行划分，快速排序按照元素的值对它们进行划分。划分是对给定数组中的元素的重新排列，使得一个数组A[i]，有s下标，A[s]左边的元素都小于等于A[s]，而所有A[s]右边的元素都大于等于A[s]。

A[0]...A[s-1],A[s],A[s+1]...A[i-1]

        显然，在对数组建立了一个划分以后，A[s]已经位于它在有序数组中的最终位置，接下来我们可以继续对A[s]前和A[s]后的子数组分别进行排序(例如，使用同样的方法)。注意，它与合并排序的不同之处在于:在合并排序算法中，将问题划分成两个子问题是很快的，算法的主要工作在于合并子问题的解;而在快速排序中，算法的主要工作在于划分阶段，而不需要再去合并子问题的解了。

伪代码

        伪代码实现

Quicksort(A[ l..r ])
//用Quicksort对子数组排序
//输入：数组A[0..n-1]中的子数组A[ l..r ]，由左右下标 l 和 r 定义

//输出：非降序排列的子数组A[ l..r ]
if l < r
        s <-Partition (A[1..r])//s是分裂位置

        Quicksort( A[ l.. (s - 1)])
        Quicksort(A[(s +1)..r ])

算法解析

        对于快速排序，有数组A[0..n-1]，子数组A[e..r]，我们要选择一个中轴，接下来会根据该元素的值来划分子数组。选择中轴有许多不同的策略，当我们分析该算法的效率时，我们会回到这个话题。现在，我们只使用最简单的策略——选择子数组的第一个元素，即p=A[0]。

        然后 我们将分别从子数组的两端进行扫描，并且将扫描到的元素与中轴相比较。从左到右的扫描(下面用指针i表示)从第二个元素开始。因为我们希望小于中轴的元素位于子数组的左半部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会停止。从右到左的扫描(下面用指针j表示)从最后一个元素开始。因为我们希望大于中轴的元素位于子数组的右半部分，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。(为什么当遇到与中轴元素相等的元素时值得停止扫描?因为当遇到有很多相同元素的数组时，这个方法可以将数组分得更加平均，从而使算法运行得更快。如果我们遇到相等元素时继续扫描，对于一个具有n个相同元素的数组来说，划分后得到的两个子数组的长度可能分别是n~1和0，从而在扫描了整个数组后只将问题的规模减1。)

        两次扫描全部停止以后，取决于扫描的指针是否相交，会发生3种不同的情况。1、如果扫描指针i和 j不相交，也就是说i<j，我们简单地交换A[i]和A[j]，再分别对i加1，对j减1，然后继续开始扫描；2、如果扫描指针相交，也就是说i> j，把中轴和A[j]交换以后，我们得到了该数组的一个划分；3、最后，如果扫描指针停下来时指向的是同一个元素，也就是说i= j，被指向元素的值一定等于p。(为什么?)因此，我们建立了该数组的一个划分，分裂点的位置s =i= j。

        我们可以把第三种情况和指针相交的情况(i> j )结合起来，只要i≥j，就交换中轴和A[j]的位置。

        下面我们来看看快速排序的视频案例

分治法_快速排序

时间效率分析

        在开始讨论快速排序的效率以前，我们应该要注意;如果扫描指针交叉了，建立划分之前所执行的键值比较次数是n+1;如果它们相等，则是n。如果所有的分裂点位于相应子数组的中点，这就是最优的情况。在最优情况下，键值比较的次数Cbes(n)满足下面的递推式:

当n>1时，{\\color{Red} C_{best}(n) = 2C_{best}(n/2)+n, C_{best}(1)=0}

        根据主定理，C_{best}(n)\\in \\Theta (nlog_{2}n)；对于n=2*的情况求得C_{best}(n) = nlog_{2}n 。

        在最差的情况下，所有的分裂点都趋于极端:两个子数组有一个为空，而另一个子数组仅仅比被划分的数组少一个元素。具体来说，这种令人遗憾的情况会发生在升序的数组上，也就是说，输入的数组已经被排过序了!的确，如果 A[0..n –1]是严格递增的数组，并且我们将A[0]作为中轴，从左到右的扫描会停在A[1]上，而从右到左的扫描会一直处理到A[0]为止，导致分裂点出现在0这个位置。

        所以，在进行了n+1次比较之后建立了划分，并且将A[0]和它本身进行了交换以后，快速排序算法还会对严格递增的数组A[1..n-1]进行排序。对规模减小了的严格递增数组的排序会一直继续到最后一个子数组A[n-2..n-1]。这种情况下，键值比较的总次数应该等于:

{\\color{Orchid} C_{best}(n) = (n+1)+n+(n-1)+...+3 = (n+1)(n+2)/2-3 \\in \\Theta (n^{2})}

源码

#include <stdio.h>// 交换两个元素的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 分区函数
int partition(int arr[], int low, int high) {// 选取最后一个元素作为基准值int pivot = arr[high];// i指向小于基准值的最后一个元素int i = (low - 1);// 遍历数组，将小于基准值的元素放到左边，大于基准值的元素放到右边for (int j = low; j <= high - 1; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}// 将基准值放到中间swap(&arr[i + 1], &arr[high]);return (i + 1);
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low < high) {// 将数组分为两部分，左边的元素都小于右边的元素int pi = partition(arr, low, high);// 递归排序左边的部分quickSort(arr, low, pi - 1);// 递归排序右边的部分quickSort(arr, pi + 1, high);}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("Sorted array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

如有小伙伴需要理解分治法思想或者合并排序，可阅读这篇文章哦

分治法实现合并排序(归并排序)，理解分治算法思想，实现分治算法的完美例子合并排序（含码源与解析）icon-default.png?t=N2N8https://blog.csdn.net/weixin_53050357/article/details/129718346?spm=1001.2014.3001.5501

网络标签：

相关问题