文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 快速排序原理及java实现 - sunSir的日志 - 网易博客
侵权投诉

快速排序原理及java实现 - sunSir的日志 - 网易博客

快速排序原理及java实现

A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
进行第一次交换后: 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找)
进行第二次交换后: 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )
进行第三次交换后: 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找)
进行第四次交换后: 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )
此时再执行第三步的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27 38 13 49
76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束
结束
图6 快速排序全过程

1)、设有N(假设N=10)个数,存放在S数组中;
2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K];
3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。
如具体数据如下,那么第一躺快速排序的过程是:
数组下标: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30

上一页第2页

你可能喜欢

  • 快速排序算法
  • JAVA编程题全集及答案
  • 冒泡排序算法
  • Java笔记
  • 操作日志
  • 银行账户管理系统
  • 数据结构算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email