python快速排序的运作过程
运作过程
1、从数列中挑出一个元素,称为基准,重新排序数列,所有元素比基准值小的摆放在基准前面。
所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区操作。
2、小于基准值元素的子数列和大于基准值元素的子数列排序。
3、递归的最底部情形,是数列的大小是零或一。
也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。
实例
#快速排序-递归 defquick_sort(alist,begin,end): #递归的终止条件是begin>=last,即数组大小为1或0 #递归终止时,数组已经排好序了 ifbegin>=end: return else: #以开头的值作为基准值,然后以基准值为界将数组分区,将分区后的左右两部分继续调用快速排序函数 mid_value=alist[begin] low=begin high=end #分别从右往左寻找小于基准值的值,从左往右寻找大于基准值的值 whilelow<high: #从右往左寻找小于基准值的值 whilelow<highandalist[high]>=mid_value: high-=1 alist[low]=alist[high] #从左往右寻找大于基准值的值 whilelow<highandalist[low]<mid_value: low+=1 alist[high]=alist[low] #循环结束时,low==high,这个位置正是基准点的位置 alist[low]=mid_value #对low左边的元素执行快速排序 quick_sort(alist,begin,low-1) quick_sort(alist,low+1,end) if__name__=='__main__': alist=[54,26,93,17,77,31,44,55,20] print(alist) quick_sort(alist,0,len(alist)-1) print(alist)
以上就是python快速排序的运作过程,希望对大家有所帮助。更多python学习指路:python基础教程
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。