Python实现桶排序与快速排序算法结合应用示例_Python

Python实现桶排序与快速排序算法结合应用示例

2020-12-19 00:59Alex Yu Python

这篇文章主要介绍了Python实现桶排序与快速排序算法结合应用,结合实例形式分析了Python快速排序及桶排序结合应用的相关实现技巧,需要的朋友可以参考下

本文实例讲述了Python实现桶排序与快速排序算法结合应用的方法。分享给大家供大家参考，具体如下：

									#-*- coding: UTF-8 -*-

									import numpy as np

									from QuickSort import QuickSort

									def BucketSort(a, n):

									  barrel = {}

									  for i in xrange(0,n):

									    barrel.setdefault(i, [])

									  min = np.min(a)

									  max = np.max(a)

									  for x in a:

									    for i in xrange(0,n-1):

									      if x >= min +i* (max - min)/n and x < min +(i +1) * (max - min)/n:

									        barrel[i].append(x)

									      elif i == n-2 and x >= min +(i +1) * (max - min)/n:

									        barrel[i+1].append(x)

									  k = 0

									  for i in xrange(0,n):

									    if len(barrel[i]) != 0:

									      arr = np.array(barrel[i])

									      QuickSort(arr, 0, len(barrel[i]) -1)

									      for x in arr:

									        a[k] = x

									        k += 1

									if __name__ == '__main__':

									  a = np.random.randint(0, 100, size = 10)

									  print "Before sorting..."

									  print "---------------------------------------------------------------"

									  print a

									  print "---------------------------------------------------------------"

									  BucketSort(a, 10)

									  print "After sorting..."

									  print "---------------------------------------------------------------"

									  print a

									  print "---------------------------------------------------------------"

快速排序QuickSort：

									#-*- coding: UTF-8 -*-

									import numpy as np

									def Partition(a, i, j):

									  x = a[i]                      #将数组的第一个元素作为初始基准位置

									  p = i                        #同时记录下该元素的位置

									  while i < j:

									    while i < j and a[j] >= x:

									      j -= 1

									    while i < j and a[i] <= x:

									      i += 1

									    if i != j:

									      a[i], a[j] = a[j], a[i]         #交换a[i]与a[j]

									  a[p], a[i] = a[i], a[p]           #将a[p]与a[i]进行交换

									  p = i                       #得到分隔位置

									  return p

									def QuickSort(a, i, j):

									  if i < j:

									    p = Partition(a, i, j)

									    QuickSort(a, i, p-1)

									    QuickSort (a, p+1, j)

									if __name__ == '__main__':

									  a = np.random.randint(0, 100, size = 100)

									  print "Before sorting..."

									  print "---------------------------------------------------------------"

									  print a

									  print "---------------------------------------------------------------"

									  QuickSort(a, 0, a.size - 1)

									  print "After sorting..."

									  print "---------------------------------------------------------------"

									  print a

									  print "---------------------------------------------------------------"