葫芦的运维日志

下一篇 搜索 上一篇

---

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

先说两句题外话，一般意义上的栈有两层含义，一层是后进先出的数据结构栈，一层是指函数的内存栈，归根结底，函数的内存栈的结构就是一个后进先出的栈。汇编代码中，调用一个函数的时候，修改的也是堆栈指针寄存器ESP，该寄存器保存的是函数局部栈的栈顶，另外一个寄存器EBP保存的是栈底。不知道与栈存储空间相对的堆存储空间，其组织结构是否也是一个完全二叉树呢？

高级语言将递归转换为迭代，用的也是栈，需要考虑两个问题:

1）栈里边保存什么？

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

栈里边保存的当然是需要迭代的函数参数，结束条件也是跟需要迭代的参数有关。对于快速排序来说，迭代的参数是数组的上边界low和下边界high，迭代结束的条件是low == high。

>>> 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。

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]

 

葫芦的运维日志

打赏

上一篇 搜索 下一篇