搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 一只逗比程序猿 > 分治算法之快速排序

分治算法之快速排序

一只逗比程序猿 2019-11-08

分治法

“凡治众如寡者,分数是也。”

                                                                                     ——孙膑

分治法是算法中经常用到的方法。可以将规模较大的问题,分解成若干个规模较小的子问题逐一解决,从而提高效率。

分治法的思路一般如下:

(1)分解:将要解决的问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题。

(2)治理:求解各个子问题。由于各个子问题与原问题形式相同,只是规模较小而已,而当子问题划分的足够小时,就可以用简单的方法解决。

(3)合并:按原问题的要求将子问题的解逐层合并构成原问题的解。

简而言之,分支发就是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

分治法的应用有很多,比如最常见的二分查找法,合并排序等,都是分治思想的典型应用。

接下来,我们来了解一下分治法的另一项应用:快速排序

快速排序

常见的排序算法和时间复杂度

说起排序方法,有很多:直接选择排序,冒泡排序,插入排序,希尔排序,堆排序等等。这些排序方法各有优劣。常见的排序方法的时间复杂度如下:

相信很多人和小编一样,每次看到这些公式代表的复杂度,完全没有任何感受。现代计算机运算速度这么快,还在乎你这点破计算量分治算法之快速排序分治算法之快速排序!先别急,让我们来看看下面的两张图,切身感受一下这些公式所代表的复杂度。

分治算法之快速排序

分治算法之快速排序

数值太小看不出各个函数之间的差距不大

分治算法之快速排序

分治算法之快速排序

当数据量(x)很大时可以看到运算量的差距会越来越大。y=x^2的增长速度更是极为可怕。常见的几种复杂度比较如下:

O(1)<O(logn(C))<O(n)<O(nlogx(n))<O(n^2)<O(n^3)<O(n^n)

作为一名合格的程序猿,还是要尽量降低自己算法的复杂度。

快速排序算法思想

假设当前待排序的序列为A[low:high],其中low<=high,如果序列的规模足够小,则直接进行排序,否则分三步处理。

(1)分解:在A[low:high]中选定一个元素A[pivot],以此为标准将要排序的两个序列A[low:pivot-1]和A[pivot+1:high],并使用序列A[low:pivot-1]中的所有元素的值小于等于A[pivot],序列R[pivot+1:high]中所有元素均大于A[pivot],此时基准元素已经位于正确的位置,无需再参加后面的排序

(2)治理:对于两个子序列A[low:pivot-1]和A[pivot+1:high]分别通过递归调用快速排序算法来进行排序。

(3)合并:由于对A[low:pivot-1]和A[pivot+1:high]的排序是原地进行的,所以在A[low:pivot-1]和A[pivot+1:high]无需做其他事,A[low:high]已经是排好序的了。

图解

例如对序列A:(38227746526831951377)进行快速排序。序列A中包含10个元素,初始时low=0,high=9(C语言角度)

第一步:初始化。另i=low,j=high,pivot=A[low]=38(基准元素随意指定,此处选取low下标指定的元素为基准元素)。

分治算法之快速排序

第二步:向左走。从j的位置向左找,直到找到小于或等于pivot的元素,找到A[8]=13,如下图所示:

分治算法之快速排序

此时,交换A[i]和A[j],i++,如下图所示:

分治算法之快速排序

分治算法之快速排序

第三步:向右走。从i的位置开始向右找,直到找到大于pivot的元素A[2]=77,A[i]和A[j]交换,j--, 如下图所示:

分治算法之快速排序

分治算法之快速排序

第四步:再向左走。从j的位置向左找,直到找到小于或等于pivot的元素,找到A[6]=31,A[i]和A[j]交换,i++, 如下图所示:

分治算法之快速排序

分治算法之快速排序

第五步:再向右走。从i的位置开始向右找,直到找到大于pivot元素A[3]=46A[i]和A[j]交换,j--, 如下图所示:

分治算法之快速排序

分治算法之快速排序

第六步:再向左走。从j的位置向左找,此时i的右边已经找不到小于或等于pivot的元了。

分治算法之快速排序

经过这一轮,基准元素38已经到达正确的位置,无需再动。将38的左边和右边分别分成两个序列,分别为A[0:2]=(13,22,31)和A[4:9]=(52,68,46,95,77,77)进行快速排序

代码实现(C++):

#include <iostream>
#define N 10
using namespace std;
void swap(int a[], int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp;}
int partition(int a[], int low, int high){ int i = low, j = high, pivot = a[low]; while (i<j) { while (i<j && a[j]>pivot) { j--; } if(i<j) swap(a, i, j); while(i<j && a[i]<=pivot) i++; if(i<j) swap(a, i, j); } return i;}
void quickSort(int a[], int low, int high){ if(low < high) { int m = partition(a, low, high); quickSort(a, low, m-1); quickSort(a, m+1, high); }}
void print_array(int a[], int len){ cout<<"["; for (int i=0;i<len;i++) { if(i==0) cout<<a[i]; else cout<<", "<<a[i]; } cout<<"]"<<endl;}
int main(){ int a[N] = {38, 22, 77, 46, 52, 68, 31, 95, 13, 77}; print_array(a, N); quickSort(a, 0, N-1); print_array(a, N); return 0;}

时间复杂度分析:

(1)最好时间复杂度

分解:划分函数partition需要扫描每个元素,每次扫描的元素个数不超过n,因此时间复杂度为O(n)

解决子问题:在最理想的情况下,每次划分将问题分解为两个规模为n/2的子问题,递归求解两个规模为n/2的子问题,所需的时间为2T(n/2),如下图所示:

分治算法之快速排序


合并:因为是合并排序,合并操作不需要时间复杂度,如下图所示:

分治算法之快速排序

所以总运行时间为:

分治算法之快速排序

当n>1时,可以递推求解:

分治算法之快速排序

所以最好的时间复杂度为O(nlog2n)

(2)最坏时间复杂度

分解:划分函数partition需要扫描每个元素每次扫描的个数不超过n,因此时间复杂度为O(n)

解决子问题:在坏的情况下,每次划分将问题分解后,基准元素的左侧(或者右侧)没有元素,基准元素的另一侧为一个规模为n-1的子问题,递归求解这个规模为n-1的子问题,所需时间为T(n-1).如下图所示:

分治算法之快速排序

合并:因为是原地排序,合并操作不需要时间复杂度。如下图所示:

分治算法之快速排序

所以,总的运行时间为:

分治算法之快速排序

当n>1时,可以递推求解如下:

所以最坏的时间复杂度为O(n2)

分治算法之快速排序

(3)平均复杂度

假设划分后基准元素的位置在第k(k∈{1,2,3,...,n})个,如下图所示:

分治算法之快速排序

则:

分治算法之快速排序

由归纳法可以得出T(n)的数量级也为(nlog2n)。所以快速排序的时间复杂度为O(nlog2n)

快速排序就合大家分享到这里,谢谢大家!下次给大家分享《神器的菲波那切数列》,请大家关注哦!


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《分治算法之快速排序》的版权归原作者「一只逗比程序猿」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注一只逗比程序猿微信公众号

一只逗比程序猿微信公众号:gh_421eae6c560c

一只逗比程序猿

手机扫描上方二维码即可关注一只逗比程序猿微信公众号

一只逗比程序猿最新文章

精品公众号随机推荐