用Python快速sorting

我对python是完全陌生的，我正试图在其中实现quicksort。 有人可以帮我完成我的代码吗？

我不知道如何连接三个数组并打印它们。

def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) if x == pivot: equal.append(x) if x > pivot: greater.append(x) sort(less) sort(pivot) sort(greater) 

Answer 1

 def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) if x == pivot: equal.append(x) if x > pivot: greater.append(x) # Don't forget to return something! return sort(less)+equal+sort(greater) # Just use the + operator to join lists # Note that you want equal ^^^^^ not pivot else: # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array. return array 

Answer 2

快速sorting，无需额外的内存（到位）

用法：

 array = [97, 200, 100, 101, 211, 107] quicksort(array) # array -> [97, 100, 101, 107, 200, 211] 

 def partition(array, begin, end): pivot = begin for i in xrange(begin+1, end+1): if array[i] <= array[begin]: pivot += 1 array[i], array[pivot] = array[pivot], array[i] array[pivot], array[begin] = array[begin], array[pivot] return pivot def quicksort(array, begin=0, end=None): if end is None: end = len(array) - 1 def _quicksort(array, begin, end): if begin >= end: return pivot = partition(array, begin, end) _quicksort(array, begin, pivot-1) _quicksort(array, pivot+1, end) return _quicksort(array, begin, end) 

Answer 3

还有一个简洁而漂亮的版本

 def qsort(arr): if len(arr) <= 1: return arr else: return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]]) 

让我来解释一下上面的代码的细节

1. select数组arr[0]的第一个元素作为数据透视表

   [arr[0]]

2. 使用List Comprehension那些数组的元素排列在不List Comprehension

   qsort([x for x in arr[1:] if x<arr[0]])

3. 使用List Comprehension将大于pivot的数组元素qsort

   qsort([x for x in arr[1:] if x>=arr[0]])

Answer 4

已经有很多答案了，但是我认为这个方法是最干净的实现：

 def quicksort(arr): """ Quicksort a list :type arr: list :param arr: List to sort :returns: list -- Sorted list """ if not arr: return [] pivots = [x for x in arr if x == arr[0]] lesser = quicksort([x for x in arr if x < arr[0]]) greater = quicksort([x for x in arr if x > arr[0]]) return lesser + pivots + greater 

你当然可以跳过把variables存储起来，然后像下面这样直接返回：

 def quicksort(arr): """ Quicksort a list :type arr: list :param arr: List to sort :returns: list -- Sorted list """ if not arr: return [] return quicksort([x for x in arr if x < arr[0]]) \ + [x for x in arr if x == arr[0]] \ + quicksort([x for x in arr if x > arr[0]]) 

Answer 5

如果我在Google中search“python quicksort implementation”，这个问题是第一个popup的结果。 我明白，最初的问题是“帮助纠正代码”，但已经有很多答案，无视这一要求：目前排在第二位的是可怕的单线和欢闹的“你被解雇”的评论，一般来说，许多不在位的实现（即使用与input列表大小成比例的额外内存）。 这个答案提供了一个原地的解决scheme，但它是为python 2.x 所以，下面是我对Rosetta Code就地解决scheme的解释，它也适用于python 3 ：

 import random def qsort(l, fst, lst): if fst >= lst: return i, j = fst, lst pivot = l[random.randint(fst, lst)] while i <= j: while l[i] < pivot: i += 1 while l[j] > pivot: j -= 1 if i <= j: l[i], l[j] = l[j], l[i] i, j = i + 1, j - 1 qsort(l, fst, j) qsort(l, i, lst) 

如果你愿意放弃就地财产，下面是另一个更好地说明快速sorting背后的基本思想的版本。 除了可读性以外，它的另外一个好处是它是稳定的 （相同的元素出现在sorting列表中，它们与未sorting列表中的顺序相同）。 这种稳定性不能满足上面提到的内存耗尽的就地实现。

 def qsort(l): if not l: return l # empty sequence case pivot = l[random.choice(range(0, len(l)))] head = qsort([elem for elem in l if elem < pivot]) tail = qsort([elem for elem in l if elem > pivot]) return head + [elem for elem in l if elem == pivot] + tail 

Answer 6

function方法：

 def qsort(list): if len(list) < 2: return list pivot = list.pop() left = filter(lambda x: x <= pivot, list) right = filter(lambda x: x > pivot, list) return qsort(left) + [pivot] + qsort(right) 

Answer 7

用Python快速sorting

在现实生活中，我们应该总是使用Python提供的内build类。 但是，了解快速sortingalgorithm是有益的 。

我的目标是打破这个问题，使读者很容易理解和复制，而不必返回参考资料。

快速sortingalgorithm基本如下：

1. select一个数据透视点。
2. 将小于（低于）枢轴的所有数据点移动到枢轴下方的位置 – 将大于或等于（高于）枢轴的那些移动到其上方的位置。
3. 将algorithm应用于主键上方和下方的区域

如果数据是随机分布的，select第一个数据点作为关键点相当于随机select。

可读示例：

首先，我们来看一个可读的例子，它使用注释和variables名来指向中间值：

 def quicksort(xs): """Given indexable and slicable iterable, return a sorted list""" if xs: # if given list (or tuple) with one ordered item or more: pivot = xs[0] # below will be less than: below = [i for i in xs[1:] if i < pivot] # above will be greater than or equal to: above = [i for i in xs[1:] if i >= pivot] return quicksort(below) + [pivot] + quicksort(above) else: return xs # empty list 

为了重申此处演示的algorithm和代码，我们将位于主轴上方的值移到右侧，将值移到左侧的主轴上，然后将这些分区传递给相同的函数以进一步sorting。

Golfed：

这可以打高尔夫球到88个字符：

 q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]]) 

要了解我们如何到达那里，请先阅读我们的可读示例，删除注释和文档string，然后在原地查找透视图：

 def quicksort(xs): if xs: below = [i for i in xs[1:] if i < xs[0]] above = [i for i in xs[1:] if i >= xs[0]] return quicksort(below) + [xs[0]] + quicksort(above) else: return xs 

现在在下面find：

 def quicksort(xs): if xs: return (quicksort([i for i in xs[1:] if i < xs[0]] ) + [xs[0]] + quicksort([i for i in xs[1:] if i >= xs[0]])) else: return xs 

现在知道了，如果返回前一个元素，否则如果它是真的，则返回下一个元素，我们有：

 def quicksort(xs): return xs and (quicksort([i for i in xs[1:] if i < xs[0]] ) + [xs[0]] + quicksort([i for i in xs[1:] if i >= xs[0]])) 

由于lambda函数返回一个epression，并且我们简化为单个expression式（尽pipe它变得越来越不可读），我们现在可以使用lambda：

 quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] ) + [xs[0]] + quicksort([i for i in xs[1:] if i >= xs[0]])) 

为了减less我们的例子，缩短函数和variables名称为一个字母，并消除不需要的空白。

 q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]]) 

请注意，这个lambda像大多数代码打高尔夫球，是相当不好的风格。

结论

这个algorithm经常在计算机科学课程中教授，并要求在面试中。 这有助于我们思考recursion和分而治之。

Quicksort在Python中不是很实用，因为我们的内置timsortalgorithm非常高效，而且我们有recursion限制。 我们希望用list.sort就地对列表进行sorting，或者使用sorted创build新的sorting列表 – 两者都采用key和reverse参数。

Answer 8

函数式编程aproach

 smaller = lambda xs, y: filter(lambda x: x <= y, xs) larger = lambda xs, y: filter(lambda x: x > y, xs) qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else [] print qsort([3,1,4,2,5]) == [1,2,3,4,5] 

Answer 9

我认为这里的两个答案都适用于提供的列表（它回答了原始问题），但如果传递包含非唯一值的数组，则会中断。 所以为了完整性，我只是指出每个小错误，并解释如何解决它们。

例如尝试使用Brioniusalgorithm对以下数组进行sorting[12,4,5,6,7,3,1,15,1]（请注意，1出现两次）。在某些时候，数组会更less以及在下一次迭代中不能分开的一对值（1,1）的相等数组， len（）> 1 …因此，您将最终得到一个无限循环

你可以通过返回数组来解决这个问题

 def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) if x == pivot: equal.append(x) if x > pivot: greater.append(x) # Don't forget to return something! return sort(less)+ equal +sort(greater) # Just use the + operator to join lists # Note that you want equal ^^^^^ not pivot else: # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array. return array 

发烧友的解决scheme也打破了，但由于不同的原因，它是缺lessrecursion行中的返回子句，这将导致在某些时候返回None并尝试将其附加到列表….

要解决它只是添加一个返回到该行

 def qsort(arr): if len(arr) <= 1: return arr else: return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]]) 

Answer 10

 def quick_sort(array): return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \ + quick_sort([x for x in array[1:] if x >= array[0]]) if array else [] 

Answer 11

 def Partition(A,p,q): i=p x=A[i] for j in range(p+1,q+1): if A[j]<=x: i=i+1 tmp=A[j] A[j]=A[i] A[i]=tmp l=A[p] A[p]=A[i] A[i]=l return i def quickSort(A,p,q): if p<q: r=Partition(A,p,q) quickSort(A,p,r-1) quickSort(A,r+1,q) return A 

Answer 12

一个“真正的”原地实现[algorithm8.9,8.11来自Michael T.Goodrich和Roberto Tamassia的Algorithm Design and Applications Book]：

 from random import randint def partition (A, a, b): p = randint(a,b) # or mid point # p = (a + b) / 2 piv = A[p] # swap the pivot with the end of the array A[p] = A[b] A[b] = piv i = a # left index (right movement ->) j = b - 1 # right index (left movement <-) while i <= j: # move right if smaller/eq than/to piv while A[i] <= piv and i <= j: i += 1 # move left if greater/eq than/to piv while A[j] >= piv and j >= i: j -= 1 # indices stopped moving: if i < j: # swap t = A[i] A[i] = A[j] A[j] = t # place pivot back in the right place # all values < pivot are to its left and # all values > pivot are to its right A[b] = A[i] A[i] = piv return i def IpQuickSort (A, a, b): while a < b: p = partition(A, a, b) # p is pivot's location #sort the smaller partition if p - a < b - p: IpQuickSort(A,a,p-1) a = p + 1 # partition less than p is sorted else: IpQuickSort(A,p+1,b) b = p - 1 # partition greater than p is sorted def main(): A = [12,3,5,4,7,3,1,3] print A IpQuickSort(A,0,len(A)-1) print A if __name__ == "__main__": main() 

Answer 13

该algorithm有4个简单的步骤：

1. 将数组分成3个不同的部分：左边，右边和右边，其中枢轴只有一个元素。 让我们select这个元素作为数组的第一个元素
2. 通过将元素与主元素进行比较来将元素附加到相应的部分。 （在评论中的解释）
3. 执行此algorithm，直到数组中的所有元素都被sorting
4. 最后joinleft + pivot + right部分

python中的algorithm代码：

 def my_sort(A): p=A[0] #determine pivot element. left=[] #create left array right=[] #create right array for i in range(1,len(A)): #if cur elem is less than pivot, add elem in left array if A[i]< p: left.append(A[i]) #the recurssion will occur only if the left array is atleast half the size of original array if len(left)>1 and len(left)>=len(A)//2: left=my_sort(left) #recursive call elif A[i]>p: right.append(A[i]) #if elem is greater than pivot, append it to right array if len(right)>1 and len(right)>=len(A)//2: # recurssion will occur only if length of right array is atleast the size of original array right=my_sort(right) A=left+[p]+right #append all three part of the array into one and return it return A my_sort([12,4,5,6,7,3,1,15]) 

用左右部分recursion地进行该algorithm。

Answer 14

对于版本Python 3.x ：使用operator模块的function样式，主要是为了提高可读性。

 from operator import ge as greater, lt as lesser def qsort(L): if len(L) <= 1: return L pivot = L[0] sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])] return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater)) 

并作为testing

 print (qsort([3,1,4,2,5]) == [1,2,3,4,5]) 

Answer 15

 def quick_sort(self, nums): def helper(arr): if len(arr) <= 1: return arr #lwall is the index of the first element euqal to pivot #rwall is the index of the first element greater than pivot #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round lwall, rwall, pivot = 0, 0, 0 #choose rightmost as pivot pivot = arr[-1] for i, e in enumerate(arr): if e < pivot: #when element is less than pivot, shift the whole middle part to the right by 1 arr[i], arr[lwall] = arr[lwall], arr[i] lwall += 1 arr[i], arr[rwall] = arr[rwall], arr[i] rwall += 1 elif e == pivot: #when element equals to pivot, middle part should increase by 1 arr[i], arr[rwall] = arr[rwall], arr[i] rwall += 1 elif e > pivot: continue return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:]) return helper(nums) 

Answer 16

在分区步骤中打印variables的完整示例：

 def partition(data, p, right): print("\n==> Enter partition: p={}, right={}".format(p, right)) pivot = data[right] print("pivot = data[{}] = {}".format(right, pivot)) i = p - 1 # this is a dangerous line for j in range(p, right): print("j: {}".format(j)) if data[j] <= pivot: i = i + 1 print("new i: {}".format(i)) print("swap: {} <-> {}".format(data[i], data[j])) data[i], data[j] = data[j], data[i] print("swap2: {} <-> {}".format(data[i + 1], data[right])) data[i + 1], data[right] = data[right], data[i + 1] return i + 1 def quick_sort(data, left, right): if left < right: pivot = partition(data, left, right) quick_sort(data, left, pivot - 1) quick_sort(data, pivot + 1, right) data = [2, 8, 7, 1, 3, 5, 6, 4] print("Input array: {}".format(data)) quick_sort(data, 0, len(data) - 1) print("Output array: {}".format(data)) 

Answer 17

另一个快速sorting实现：

 # A = Array # s = start index # e = end index # p = pivot index # g = greater than pivot boundary index def swap(A,i1,i2): A[i1], A[i2] = A[i2], A[i1] def partition(A,g,p): # O(n) - just one for loop that visits each element once for j in range(g,p): if A[j] <= A[p]: swap(A,j,g) g += 1 swap(A,p,g) return g def _quicksort(A,s,e): # Base case - we are sorting an array of size 1 if s >= e: return # Partition current array p = partition(A,s,e) _quicksort(A,s,p-1) # Left side of pivot _quicksort(A,p+1,e) # Right side of pivot # Wrapper function for the recursive one def quicksort(A): _quicksort(A,0,len(A)-1) A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1] print(A) quicksort(A) print(A) 

Answer 18

 def quicksort(items): if not len(items) > 1: return items items, pivot = partition(items) return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:]) def partition(items): i = 1 pivot = 0 for j in range(1, len(items)): if items[j] <= items[pivot]: items[i], items[j] = items[j], items[i] i += 1 items[i - 1], items[pivot] = items[pivot], items[i - 1] return items, i - 1 

Answer 19

插入sorting

 def qsort(a, b=0, e=None): # partitioning def part(a, start, end): p = start for i in xrange(start+1, end): if a[i] < a[p]: a[i], a[p+1] = a[p+1], a[i] a[p+1], a[p] = a[p], a[p+1] p += 1 return p if e is None: e = len(a) if eb <= 1: return p = part(a, b, e) qsort(a, b, p) qsort(a, p+1, e) 

无recursion：

 deq = collections.deque() deq.append((b, e)) while len(deq): el = deq.pop() if el[1] - el[0] > 1: p = part(a, el[0], el[1]) deq.append((el[0], p)) deq.append((p+1, el[1])) 

Answer 20

而不是采取三个不同的arrays较小的相等更大，然后连接所有尝试传统的概念（分区方法）：

http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

这是不使用任何内置function。

分区function –

 def partitn(alist, left, right): i=left j=right mid=(left+right)/2 pivot=alist[mid] while i <= j: while alist[i] < pivot: i=i+1 while alist[j] > pivot: j=j-1 if i <= j: temp = alist[i] alist[i] = alist[j] alist[j] = temp i = i + 1 j = j - 1 

Answer 21

1. 首先我们声明数组中的第一个值是pivot_value，我们也设置了左右标记
2. 我们创build第一个while循环，这个while循环在那里告诉分区进程在不满足必要条件时再次运行
3. 那么我们应用分区过程
4. 在两个分区进程都运行之后，我们检查它是否满足适当的条件。 如果是这样，我们将其标记为完成，如果不是，我们切换左值和右值并再次应用
5. 一旦完成切换左侧和右侧的值，并返回split_point

我附上下面的代码！ 由于枢轴值的位置，这个快速sorting是一个很好的学习工具。 既然它处于一个不变的地方，你可以多次遍历它，并真正掌握它是如何工作的。 在实践中，最好随机化枢轴以避免O（N ^ 2）运行时间。

 def quicksort10(alist): quicksort_helper10(alist, 0, len(alist)-1) def quicksort_helper10(alist, first, last): """ """ if first < last: split_point = partition10(alist, first, last) quicksort_helper10(alist, first, split_point - 1) quicksort_helper10(alist, split_point + 1, last) def partition10(alist, first, last): done = False pivot_value = alist[first] leftmark = first + 1 rightmark = last while not done: while leftmark <= rightmark and alist[leftmark] <= pivot_value: leftmark = leftmark + 1 while leftmark <= rightmark and alist[rightmark] >= pivot_value: rightmark = rightmark - 1 if leftmark > rightmark: done = True else: temp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = temp temp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = temp return rightmark 

Answer 22

 def quick_sort(l): if len(l) == 0: return l pivot = l[0] pivots = [x for x in l if x == pivot] smaller = quick_sort([x for x in l if x < pivot]) larger = quick_sort([x for x in l if x > pivot]) return smaller + pivots + larger 

Answer 23

 def quick_sort(list): if len(list) ==0: return [] return quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ] + quick_sort( filter( lambda item: item > list[0], list)) 

Answer 24

或者，如果您更喜欢单线程，也可以说明C / C ++ varags，lambdaexpression式以及expression式的Python等价物：

 qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])