菜鸟教程 -- 学的不仅是技术，更是梦想！

Python 3 教程

Python 计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

实例

def countSort(arr): output = [0 for i in range(256)] count = [0 for i in range(256)] ans = ["" for _ in arr] for i in arr: count[ord(i)] += 1 for i in range(256): count[i] += count[i-1] for i in range(len(arr)): output[count[ord(arr[i])]-1] = arr[i] count[ord(arr[i])] -= 1 for i in range(len(arr)): ans[i] = output[i] return ans arr = "wwwrunoobcom" ans = countSort(arr) print ( "字符数组排序 %s" %("".join(ans)) )

执行以上代码输出结果为：

符数组排序 bcmnoooruwww

Document 对象参考手册 Python3 实例

Python 堆排序

Python 希尔排序

1 篇笔记写笔记

减少循环次数参考:

def countSort(arr):
   count = [ 0 for i in range(256)]
   output = ["" for _ in arr]
   mx, mn = 0, 255
   for i in arr:
      idx = ord(i)
      if idx > mx: mx = idx
      if idx < mn: mn = idx
      count[idx] += 1
   idx = 0
   for i in range(mn, mx + 1):
      if count[i] == 0: continue
      for _ in range(count[i]):
         output[idx] = chr(i)
         idx += 1
   return output
arr = "wwwrunoobcom"
ans = countSort(arr) 
print ( "字符数组排序 %s"  %("".join(ans)) )

leaf_cq2个月前 (09-02)