首頁 後端開發 Python教學 python算法学习之计数排序实例

python算法学习之计数排序实例

Jun 06, 2016 am 11:29 AM
計數排序

python算法学习之计数排序实例

代码如下:


# -*- coding: utf-8 -*-

def _counting_sort(A, B, k):
    """计数排序,伪码如下:
    COUNTING-SORT(A, B, k)
    1  for i ← 0 to k // 初始化存储区的值
    2    do C[i] ← 0
    3  for j ← 1 to length[A] // 为各值计数
    4    do C[A[j]] ← C[A[j]] + 1
    5  ▷ C[i]包含等于i的元素个数
    6  for i ← 1 to k // 求计数和,确定    7    do C[i] ← C[i] + C[i-1]
    8  ▷ C[i]包含小于或等于i的元素个数
    9  for j ← length[A] downto 1
    10   do B[C[A[j]]] ← A[j] // 将A[j]值放到对应位置
    11      C[A[j]] ← C[A[j]] - 1 // 避免元素相同时覆盖同一位置

    T(n) = θ(n)

    Args:
        A (Sequence): 原数组
        B (Sequence): 结果数组
        k (int): 值上限,假定了所有元素介于[0,k]
    """
    len_c = k + 1
    C = [0] * len_c
    for a in A:
        C[a] = C[a] + 1
    for i in range(1, len_c):
        C[i] = C[i] + C[i-1]
    for a in A[::-1]:
        B[C[a]-1] = a
        C[a] = C[a] - 1

def counting_sort(A):
    """假定A数组所有元素都介于[0,len(A)-1]"""
    B = [0] * len(A)
    _counting_sort(A, B, len(A) - 1)
    return B

if __name__ == '__main__':
    import random, timeit

    items = range(10000)
    random.shuffle(items)

    def test_sorted():
        print(items)
        sorted_items = sorted(items)
        print(sorted_items)

    def test_counting_sort():
        print(items)
        sorted_items = counting_sort(items)
        print(sorted_items)

    test_methods = [test_sorted, test_counting_sort]
    for test in test_methods:
        name = test.__name__ # test.func_name
        t = timeit.Timer(name + '()', 'from __main__ import ' + name)
        print(name + ' takes time : %f' % t.timeit(1))

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱門文章

倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章

倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章標籤

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

如何使用Python查找文本文件的ZIPF分佈 如何使用Python查找文本文件的ZIPF分佈 Mar 05, 2025 am 09:58 AM

如何使用Python查找文本文件的ZIPF分佈

我如何使用美麗的湯來解析HTML? 我如何使用美麗的湯來解析HTML? Mar 10, 2025 pm 06:54 PM

我如何使用美麗的湯來解析HTML?

python中的圖像過濾 python中的圖像過濾 Mar 03, 2025 am 09:44 AM

python中的圖像過濾

如何使用TensorFlow或Pytorch進行深度學習? 如何使用TensorFlow或Pytorch進行深度學習? Mar 10, 2025 pm 06:52 PM

如何使用TensorFlow或Pytorch進行深度學習?

Python中的平行和並發編程簡介 Python中的平行和並發編程簡介 Mar 03, 2025 am 10:32 AM

Python中的平行和並發編程簡介

python對象的序列化和避難所化:第1部分 python對象的序列化和避難所化:第1部分 Mar 08, 2025 am 09:39 AM

python對象的序列化和避難所化:第1部分

如何在Python中實現自己的數據結構 如何在Python中實現自己的數據結構 Mar 03, 2025 am 09:28 AM

如何在Python中實現自己的數據結構

Python中的數學模塊:統計 Python中的數學模塊:統計 Mar 09, 2025 am 11:40 AM

Python中的數學模塊:統計

See all articles