资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
亲,该文档总共4页全部预览完了,如果喜欢就下载吧!
资源描述
python 实现快速排序的几种方法快速排序算法说明:设要排序的数组是 A0AN-1,首先任意选取一个数据(通常选用中间的数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是:1)设置两个变量 i、j,排序开始的时候:i=0,j=N-1;2)以第一个数组元素作为关键数据,赋值给 key,即 key=A0;3)从 j 开始向前搜索,即由后开始向前搜索(j - ),找到第一个小于 key 的值 Aj;4)从 i 开始向后搜索,即由前开始向后搜索(i + ),找到第一个大于 key 的 Ai,Ai与 Aj交换;5)重复第 3、4、5 步,直到 I=J; (3,4 步中,没找到符合条件的值,即 3 中 Aj不小于 key,4 中 Aj不大于 key 的时候改变 j、i 的值,使得 j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候 i, j 指针位置不变。另外,i=j 这一过程一定正好是 i+或 j-完成的时候,此时令循环结束)。(注:以上说明摘自百度百科)方法一:经典快速排序算法下面的代码中是经典快速排序算法,并且范围正序和倒序两种排列方式:#正序排列函数def qiucksortasc(arr,begin,end):#设定取出开始的第一个值用于判断key=arrbegin#从左边开始找大于 key 值的元素下标pl=begin#从右边开始找小于 key 值的元素下标pr=endwhile 1:#找到从右边开始第一个小于 key 的元素,如果大于 key,pr-1 继续寻找while arrprkey:pr=pr-1#找到从左边开始第一个大于 key 的元素,如果小于 key,pl+1 继续寻找while arrplbegin):qiucksortasc(arr,begin,pr-1)#倒序排列函数def qiucksortdesc(arr,begin,end):#设定取出开始的第一个值用于判断key=arrbegin#从左边开始找大于 key 值的元素下标pl=begin#从右边开始找小于 key 值的元素下标pr=endwhile 1:#找到从右边开始第一个大于 key 的元素,如果小于 key,pr-1 继续寻找while arrprkey:pl=pl+1#交换 arrpr和 arrpl的值arrpl,arrpr=arrpr,arrplprint pl is %d and pr is %d %(pl,pr), and ,arr#当 pr 和 pl 相等的时候跳出循环if pl=pr:print 完成一趟快排 break;#递归开始#对 key 左边的元素开始排序if(pl-1begin):qiucksortdesc(arr,begin,pl-1)#对 key 右边的元素开始排序 if(pr+1=arr0)a=4,2,1,5,3,7,6b=qiucksortshort(a)print 原数组为:,aprint 排序后数组为:,b结果输出为:原数组为: 4, 2, 1, 5, 3, 7, 6排序后数组为: 1, 2, 3, 4, 5, 6, 7
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号