python_计数排序counting_sort()

python_计数排序counting_sort()

文章目录

​​计数排序是非比较排序,牺牲空间换取时间(Linear Time)​​​​code(adapted from Introduction to Alogrithm)​​

计数排序是非比较排序,牺牲空间换取时间(Linear Time)

code(adapted from Introduction to Alogrithm)

'''Description: Version: 2.0Author: xuchaoxinDate: 2021-03-26 20:58:42LastEditors: xuchaoxinLastEditTime: 2021-03-26 23:07:59'''""" for i ← 1 to kdo C[i] ← 0for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳C[i] = |{key = i}|for i ← 2 to kdo C[i] ← C[i] + C[i–1] ⊳C[i] = |{key ≤ i}|for j ← n down_to 1do B[C[A[ j]]] ← A[ j]C[A[ j]] ← C[A[ j]] – 1"""def counting_sort(A): """counting_sort(),stable sort algorithm; the function apply to natural numbers,but: if you want to sort float,then times all the elements a positive integer big enough to make them natural numbers if you want to sort negative numbers,you can plus all of the element a positive big enough to make them natural numbers Args: A (List): list/array to be sort """ sizeOfA = len(A) # n max_element = max(A) # k count_list = [] result_list = [] """ initial the counting list """ for i in range(0, max_element+1): # A[i]=0 count_list.append(0) # result_list.append(0) for i in range(0, sizeOfA): result_list.append(0) """ counting values:(it's ok) """ for i in range(0, sizeOfA): count_list[A[i]] += 1 """ update the values(element) after the second element in the count_list; however,the indice start from 0,so substract 1 at first """ count_list[0] -= 1 for i in range(1, max_element+1): count_list[i] += (count_list[i-1]) """ insert the element of A(A[i]) to correct place in the sorting sequence """ for i in range(sizeOfA-1, -1, -1): """ in order to find the cause :IndexError: list assignment index out of range I print some value to locate it(comment out the program statement),the cause is that I didn't initial the list:result_list""" # print("i=",i) # print("A[i]=",A[i]) # print("len(count_list)=",len(count_list)) # print("") result_list[count_list[A[i]]] = A[i] """ update the indice of count_list:namely,the value which indice=A[i]:count_list[A[i]] """ count_list[A[i]] -= 1 return result_listdef main(): """ test the counting_sort() """ print(counting_sort([4, 2, 2, 6, 9, 0, 1]))# main()

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。