快速排序算法的时间复杂度 快速排序
大家好,我是小典,我来为大家解答以上问题。快速排序算法的时间复杂度,快速排序,很多人还不知道,现在让我们一起来看看吧!
1、设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:
2、 1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;
3、 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
4、 3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与A[I]交换;
5、 4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与A[J]交换;
6、 5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)
7、 例如:待排序的数组A的值分别是:(初始关键数据:X=49) 注意关键X永远不变,永远是和X进行比较,无论在什么位子,最后的目的就是把X放在中间,小的放前面大的放后面。
8、 A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]:
9、 49 38 65 97 76 13 27
10、 进行第一次交换后: 27 38 65 97 76 13 49
11、 ( 按照算法的第三步从后面开始找)
12、 进行第二次交换后: 27 38 49 97 76 13 65
13、 ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时:I=3 )
14、 进行第三次交换后: 27 38 13 97 76 49 65
15、 ( 按照算法的第五步将又一次执行算法的第三步从后开始找
16、 进行第四次交换后: 27 38 13 49 76 97 65
17、 ( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时:I=4,J=6 )
18、 此时再执行第三步的时候就发现I=J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。
19、 快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:
20、 初始状态 {49 38 65 97 76 13 27}
21、 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
22、 分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。
23、 {76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。
本文到此讲解完毕了,希望对大家有帮助。
免责声明:本文由用户上传,如有侵权请联系删除!
猜你喜欢
最新文章
- 数字媒体艺术是什么学 数字媒体艺术是什么
- 赋权执法 赋权
- 知心爱人歌词歌谱 知心爱人歌词
- 耐组词有哪些二年级 耐组词有哪些
- 方兴未艾拼音是什么 方兴未艾的读音
- 朱正廷几岁 朱正廷多少岁
- 生字笔顺图片 生字笔顺
- wonder怎么读的英语 wonder怎么读
- 天气丹属于什么档次 韩后属于什么档次
- 芳草集洗面奶怎么样 芳草集隔离霜
- 刘亦菲为什么叫神仙 刘亦菲为什么叫刘八条
- 人稀成语 人成语
- 积什么成什么四字词语 积什么成什么
- 什么风骤雨的成语 什么风骤雨
- 冻粉对人身体有害吗 冻粉
- 水中月镜中花袅袅炊烟无牵挂放不下江南烟雨如画 水中月镜中花
- 卖火柴的小女孩选自安徒生的什么书 卖火柴的小女孩选自
- 李字成语 李成语
- 微信能恢复聊天记录吗? 微信能恢复聊天记录吗
- 油菜蘑菇的做法窍门 油菜蘑菇的做法
- 烂开头的成语接龙有哪些词语 烂开头的成语接龙
- 叫龙02 叫龙
- 青岛湛山寺门票预约官网 青岛湛山寺
- entail entails