欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python递归实现快速排序

程序员文章站 2022-05-30 20:42:05
快速排序(quicksort)是对冒泡排序的一种改进: 基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然...

快速排序(quicksort)是对冒泡排序的一种改进:

基本思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序

过程可以递归进行,以此达到整个数据变成有序序列。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=n-1;

2)以第一个数组元素作为关键数据,赋值给key,即key=a[0];

3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值a[j],将a[j]和a[i]互换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的a[i],将a[i]和a[j]互换;

5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中a[j]不小于key,4中a[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,

进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

利用python实现的快速排序代码quick_sort.py如下:

def sub_sort(array,low,high):
  pivotkey=array[low]
  while low<high :
    while low<high and array[high]>=pivotkey:
      high -= 1
    array[low]=array[high]
    while low<high and array[low]<=pivotkey:
      low += 1
    array[high]=array[low]
  array[low]=pivotkey
  return low
 
def quick_sort(array,low,high):
  if low < high :
    pivoloc=sub_sort(array,low,high)
    quick_sort(array,low,pivoloc-1)
    quick_sort(array,pivoloc+1,high)
 
if __name__=="__main__": 
  array=[49,38,65,97,76,13,27]
  print array
  quick_sort(array,0,len(array)-1)
  print array

对一个数组array=[49, 38, 65, 97, 76, 13, 27]进行快速排序,得到的结果如下所示:

=============== restart: i:\python_datastructure\quick_sort.py ===============
[49, 38, 65, 97, 76, 13, 27]
[13, 27, 38, 49, 65, 76, 97]
>>> 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。