# python 快排算法

## 一.用栈实现非递归的快排程序

1）栈里边保存什么？

2）迭代结束的条件是什么？

```>>> def quick_sort(array, l, r):
...      if l >= r:
...          return
...      stack = []
...      stack.append(l)
...      stack.append(r)
...      while stack:
...          low = stack.pop(0)
...          high = stack.pop(0)
...          if high - low <= 0:
...              continue
...          x = array[high]
...          i = low - 1
...          for j in range(low, high):
...              print 'array[j] <= x:',array[j],x
...              if array[j] <= x:
...                  i += 1
...                  print 'array[i], array[j] = array[j], array[i]:',array[i], array[j]
...                  array[i], array[j] = array[j], array[i]
...          array[i + 1], array[high] = array[high], array[i + 1]
...          print '[low, i, i + 2, high]:',[low, i, i + 2, high]
...          stack.extend([low, i, i + 2, high])
...
>>>
>>> myList = [49,38,65,97,76,13,27,49]
>>> quick_sort(myList,0,7)
array[j] <= x: 49 49
array[i], array[j] = array[j], array[i]: 49 49
array[j] <= x: 38 49
array[i], array[j] = array[j], array[i]: 38 38
array[j] <= x: 65 49
array[j] <= x: 97 49
array[j] <= x: 76 49
array[j] <= x: 13 49
array[i], array[j] = array[j], array[i]: 65 13
array[j] <= x: 27 49
array[i], array[j] = array[j], array[i]: 97 27
[low, i, i + 2, high]: [0, 3, 5, 7]
array[j] <= x: 49 27
array[j] <= x: 38 27
array[j] <= x: 13 27
array[i], array[j] = array[j], array[i]: 49 13
[low, i, i + 2, high]: [0, 0, 2, 3]
array[j] <= x: 65 76
array[i], array[j] = array[j], array[i]: 65 65
array[j] <= x: 97 76
[low, i, i + 2, high]: [5, 5, 7, 7]
array[j] <= x: 49 38
[low, i, i + 2, high]: [2, 1, 3, 3]
>>> myList
[13, 27, 38, 49, 49, 65, 76, 97]```

## 二.只用了一层循环，并且一趟就完成分片，相比之下代码要简洁的多了。

```>>> def quick_sort(array, l, r):
...     if l < r:
...         q = partition(array, l, r)
...         quick_sort(array, l, q - 1)
...         quick_sort(array, q + 1, r)
...
>>> def partition(array, l, r):
...     x = array[r]
...     i = l - 1
...     for j in range(l, r):
...         if array[j] <= x:
...             i += 1
...             array[i], array[j] = array[j], array[i]
...     array[i + 1], array[r] = array[r], array[i+1]
...     return i + 1
...
>>> a=[3,2,1,5,8,9]
>>> quick_sort(a,0,5)
>>> a
[1, 2, 3, 5, 8, 9]```

## 三.一行实现快排:

```>>> quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
>>> array=[3,2,1,5,9,8]
>>> quick_sort(array)
[1, 2, 3, 5, 8, 9]```

## array如果是个列表的话，可以通过len(array)求得长度，但是后边递归调用的时候必须使用分片，而分片执行的原列表的复制操作，这样就达不到原地排序的目的了，所以还是要传上边界和下边界的

```>>> def QuickSort(myList,start,end):
...     #判断low是否小于high,如果为false,直接返回
...     if start < end:
...         i,j = start,end
...         #设置基准数
...         base = myList[i]
...         while i < j:
...             #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
...             while (i < j) and (myList[j] >= base):
...                 j = j - 1
...             #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
...             myList[i] = myList[j]
...             #同样的方式比较前半区
...             while (i < j) and (myList[i] <= base):
...                 i = i + 1
...             myList[j] = myList[i]
...         #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
...         myList[i] = base
...         #递归前后半区
...         QuickSort(myList, start, i - 1)
...         QuickSort(myList, j + 1, end)
...     return myList
...
>>> myList = [49,38,65,97,76,13,27,49]
>>> print("Quick Sort: ")
Quick Sort:
>>> QuickSort(myList,0,len(myList)-1)
[13, 27, 38, 49, 49, 65, 76, 97]```

0 条评论

• ### linux nginx服务器域名泛解析配置

要配置泛解析域名就需要先到网站所在的DNS服务商处设置A记录。 列如要解析www.liezi.net，请在主机记录(RR)处填写www 常见命名前缀...

• ### python--几种快速排序的实现以及运行时间比较

快速排序的基本思想：首先选定一个数组中的一个初始值，将数组中比该值小的放在左边，比该值大的放在右边，然后分别对左边的数组进行如上的操作，对右边的数组进行如上的操...

• ### 快速排序的四种python实现

快速排序算法，简称快排，是最实用的排序算法，没有之一，各大语言标准库的排序函数也基本都是基于快排实现的。

• ### PHP数组array类常见操作示例

array_diff(arr1,arr2);//计算数组的差集（对比返回在 array1 中但是不在 array2 及任何其它参数数组中的值。）

• ### python list定义并初始化长度

使用Python的人都知道range()函数很方便，今天再用到它的时候发现了很多以前看到过但是忘记的细节。这里记录一下range(),复习下list的slid...

• ### 冒泡排序算法（Bubble Sort）

对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组的前面，把大的元素移动到