搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 大学生活必备 > 详解快速排序算法(数据结构考研)

详解快速排序算法(数据结构考研)

大学生活必备 2019-11-08

动画获取方式

数据结构全部动画演示过程动画

链接:

https://pan.baidu.com/s/1vt79e2h7qwXkkZmi_vhv_Q 

提取码:2ffa

详解快速排序算法(数据结构考研)
详解快速排序算法(数据结构考研)
详解快速排序算法(数据结构考研)

算法思想

快速排序使用分治的思想,通过一趟排序将待排序列分割成两部分,其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

实现步骤

1、选择基准

严奶奶书中选择第一个元素作为基准(pivot),但是实际过程中,选择中间元素可能会更好。

2、分割操作

以该基准在序列中的实际位置,把序列分成两个子序列。此时,在基准左边的元素都比该基准小,在基准右边的元素都比基准大

3、递归地对两个序列进行快速排序,直到序列为空或者只有一个元素。


算法详解

void QuickSort ( T a[], int low, int high ) {    

if ( low < high ) {     

// 划分      

pivot = a[low];     

i = low; 

j = high;     

while ( i < j ) {        

while ( i<j && a[j] >= pivot )  

j--;       

a[i] = a[j];        

while ( i<j && a[i] <= pivot )  

i++;       

a[j] = a[i];   

}      

a[i] = pivot;      

// 对子序列快排     

QuickSort ( a, low, i-1);     

QuickSort ( a, i+1, high);     

} 

}

性能分析

平均情况下,时间复杂度O(nlogn)。记录本来有序时为最坏情况,时间复杂度为O(n2 )。 

空间复杂度(考虑递归调用的最大深度)在平均情况下为O(logn),在最坏情况下为O(n)。 

快速排序是不稳定的。


习题实战

练习

{52  49  80  36  14  58   61} 快速排序

快速排序一趟的详解

详解快速排序算法(数据结构考研)

技巧:  选第1个记录为轴,分别从后向前,从前向后扫描记录,后面“抓大放小”(如:①②),前面“抓小放大”(如:③④),交替进行(⑤-⑦),最后将轴记录放在中间(⑧),划分成两个序列。

整个快速排序过程

详解快速排序算法(数据结构考研)



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《详解快速排序算法(数据结构考研)》的版权归原作者「大学生活必备」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注大学生活必备微信公众号

大学生活必备微信公众号:dxs_bb

大学生活必备

手机扫描上方二维码即可关注大学生活必备微信公众号

大学生活必备最新文章

精品公众号随机推荐