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

2019-11-25 15:38:30

字体：大中小

来源：转载

供稿：网友

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

#-*- coding: UTF-8 -*-import numpy as npfrom QuickSort import QuickSortdef 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 += 1if __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 npdef 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 pdef 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 "---------------------------------------------------------------"

程序运行结果：