比較型排序與非比較型排序算法的總結(jié)

排序方法

冒泡排序

In [1]:

def insert_sort(array):
    # 這個(gè)i表示該找第i+1大的數(shù)
    for i in xrange(len(array)-1):
        for j in xrange(0,len(array)-i-1):
            if array[j]>array[j+1]:
                array[j+1],array[j] = array[j],array[j+1]

    return array

array = [12,18,29,9,4,1,6]
bubleSort(array)

Out[1]:

[1, 4, 6, 9, 12, 18, 29]

In [21]:

def bubleSort2(array):
    # 這個(gè)i該找存在這個(gè)下標(biāo)上的數(shù)了
    for i in xrange(len(array)-1,0,-1):
        for j in xrange(0,i):
            if array[j]>array[j+1]:
                array[j+1],array[j] = array[j],array[j+1]

    return array

array = [12,18,29,9,4,1,6]
bubleSort(array)

Out[21]:

[1, 4, 6, 9, 12, 18, 29]

復(fù)雜度分析

平均情況與最壞情況均為 $O(n^2)$, 使用了 temp 作為臨時(shí)交換變量厕妖,空間復(fù)雜度為 $O(1)$.

選擇排序

核心:不斷地選擇剩余元素中的最小者。

  1. 找到數(shù)組中最小元素并將其和數(shù)組第一個(gè)元素交換位置轻专。
  2. 在剩下的元素中找到最小元素并將其與數(shù)組第二個(gè)元素交換疆液,直至整個(gè)數(shù)組排序寺擂。

性質(zhì):

  1. 比較次數(shù)=(N-1)+(N-2)+(N-3)+...+2+1~N^2/2
  2. 交換次數(shù)=N
  3. 運(yùn)行時(shí)間與輸入無(wú)關(guān)
  4. 數(shù)據(jù)移動(dòng)最少

In [9]:

def selectSort(array):
    # 這里i記得是這次該決定誰(shuí)存到這個(gè)下標(biāo)上了
    for i in xrange(len(array)-1):
        min_ind = i
        for j in xrange(i+1,len(array)):
            if array[min_ind]>array[j]:
                min_ind = j
        if min_ind != i:
            array[min_ind],array[i] = array[i],array[min_ind]

    return array

array = [12,18,29,9,4,1,6]
selectSort(array)

Out[9]:

[1, 4, 6, 9, 12, 18, 29]

In [1]:

def selectSort2(array):
    # 這里i記得是這次該決定誰(shuí)存到這個(gè)下標(biāo)上了
    for i in xrange(len(array)-1,0,-1):
        max_ind = i
        #print i
        for j in xrange(0,i):
            #print j,array[max_ind],array[j]
            if array[max_ind]<array[j]:
                max_ind = j
        if max_ind != i:
            array[max_ind],array[i] = array[i],array[max_ind]
        #print array
    return array

array = [12,18,29,9,4,1,6]
selectSort2(array)

Out[1]:

[1, 4, 6, 9, 12, 18, 29]

插入排序

In [1]:

def insertSort(alist):
    for i,item_i in enumerate(alist):
        # 開(kāi)始確定第i個(gè)元素應(yīng)該在的位子;
        index = i-1
        # 從前一個(gè)元素開(kāi)始,遍歷到0,
        while index>=0 and alist[index]>item_i:
            alist[index+1]=alist[index]
            index-=1
        alist[index+1] = item_i
    return alist

alist = [12,18,29,9,4,1,6]
insertSort(alist)

Out[1]:

[1, 4, 6, 9, 12, 18, 29]

希爾排序

其實(shí)就是分組插入排序

In [7]:

def shellSort(alist):
    n = len(alist)
    gap = int(round(n/2)) # 去長(zhǎng)度的一般作為gap
    while gap>0:
        # print gap
        for i in xrange(gap,n):
            # 把i插入該列前面已經(jīng)排好的地方 
            temp = alist[i]
            while i-gap >=0 and alist[i-gap]>temp:
                alist[i]=alist[i-gap]
                i-=gap
            alist[i] = temp
        gap = int(round(gap/2)) # 得到新的步長(zhǎng)
    return alist

array = [12,18,29,9,4,1,6]
shellSort(array)

Out[7]:

[1, 4, 6, 9, 12, 18, 29]

歸并排序

核心:將兩個(gè)有序?qū)?shù)組歸并成一個(gè)更大的有序數(shù)組。通常做法為遞歸排序屈藐,并將兩個(gè)不同的有序數(shù)組歸并到第三個(gè)數(shù)組中奶赠。歸并排序是一種典型的分治應(yīng)用鱼填。

分兩步:分段 / 合并

時(shí)間復(fù)雜度為$ O(NlogN)$, 使用了等長(zhǎng)的輔助數(shù)組,空間復(fù)雜度為 $O(N)$毅戈。

In [5]:

def mergeSort(alist):
    if(len(alist) <=1 ):
        return alist
    mid   = len(alist)/2
    left  = mergeSort(alist[:mid])
    right = mergeSort(alist[mid:])
    return combine(left,right)

def combine(left,right):
    alist = []
    l = 0
    r = 0

    while l<len(left) and r<len(right):
        if left[l]<=right[r]:
            alist.append(left[l])
            l+=1
        else:
            alist.append(right[r])
            r+=1

    while l<len(left):
        alist.append(left[l])
        l+=1

    while r<len(right):
        alist.append(right[r])
        r+=1

    return alist

unsortedArray = [6, 5,27, 3, 41,1, 8, 12,7, 2, 4,18]
mergeSort(unsortedArray)

Out[5]:

[1, 2, 3, 4, 5, 6, 7, 8, 12, 18, 27, 41]

quick-sort 快速排序

核心:快排是一種采用分治思想的排序算法苹丸,大致分為三個(gè)步驟。

  1. 定基準(zhǔn)——首先隨機(jī)選擇一個(gè)元素最為基準(zhǔn)
  2. 劃分區(qū)——所有比基準(zhǔn)小的元素置于基準(zhǔn)左側(cè)苇经,比基準(zhǔn)大的元素置于右側(cè)
  3. 遞歸調(diào)用——遞歸地調(diào)用此切分過(guò)程

out-in-place 非原地排序

『遞歸 + 非原地排序』的實(shí)現(xiàn)雖然簡(jiǎn)單易懂赘理,但是如此一來(lái)『快速排序』便不再是最快的通用排序算法了,因?yàn)檫f歸調(diào)用過(guò)程中非原地排序需要生成新數(shù)組扇单,空間復(fù)雜度頗高商模。list comprehension 大法雖然好寫(xiě),但是用在『快速排序』算法上就不是那么可取了。

In [1]:

def qsort1(alist):
    if len(alist)<=1:
        return alist
    privot = alist[0]

    # 下面的做法用到了list的合并施流,這些語(yǔ)言底層其實(shí)沒(méi)什么計(jì)數(shù)含量
    # 完全可以用高級(jí)語(yǔ)言的庫(kù)取代响疚,我沒(méi)有必要去實(shí)現(xiàn)這些底層
    return qsort1([item for item in alist[1:] if item<privot]) + \
            [privot] + \
            qsort1([item for item in alist[1:] if item>privot])

unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
print(qsort1(unsortedArray))        
[1, 2, 3, 4, 5, 6, 7, 8]

非原地排序復(fù)雜度分析

在最好的情況下,快速排序的基準(zhǔn)元素正好是正好是整個(gè)數(shù)組的中位數(shù)瞪醋,可以近似為二分忿晕,最好情況下遞歸的層數(shù)為$logn$.

那么對(duì)于遞歸非原地快排來(lái)說(shuō),最好的情況下趟章,每往下遞歸一層杏糙,所需要的存儲(chǔ)空間是上一層的一半,完成最底層調(diào)用后就向上返回執(zhí)行出棧操作,故并不需要保存本層所有元素的值(空間重用)蚓土,所以需要的存儲(chǔ)空間就是 $ \sum^{log_2n}_{i=0} \frac{n}{2^i} = n2(1-\frac{1}{n}) = 2n$

hehe
hehe

那么最壞的情況就是宏侍,每次選的基準(zhǔn)元素就是整個(gè)數(shù)組的最值,這樣遞歸的層數(shù)就是n-1次

那么對(duì)于遞歸非原地快排來(lái)說(shuō)蜀漆,最壞的情況是第i層的空間位n-i+1,總的空間位$ \sum^{n-1}_{i=0} n-i+1= \frac{n(n+1)}{2}=O(n^2) $


in-palce 原地排序

過(guò)程中控制4個(gè)下標(biāo):

  • l 待排序部分的下界
  • u 待排序部分的上界
  • m 不大于基準(zhǔn)元素的最后一個(gè)位置谅河,在遍歷結(jié)束后與基準(zhǔn)元素位置交換
  • i 遍歷的元素下標(biāo),從l到u

In [2]:

def qsort2(alist,l,u):
    # 遞歸結(jié)束條件
    if l>=u:
        return 

    # 初始化幾個(gè)下標(biāo)
    m=l

    privot = alist[l]
    for i in xrange(l+1,u+1):
        if alist[i]<privot:
            m+=1
            # 把比基準(zhǔn)元素小的挪到前半部分
            alist[m],alist[i] = alist[i],alist[m]

    alist[m],alist[l] = alist[l],alist[m]

    qsort2(alist,l,m-1) #
    qsort2(alist,m+1,u) #必須這樣否則如果序列已經(jīng)是有序的就會(huì)進(jìn)入死循環(huán)

    return alist

unsortedArray = [6, 5, 3, 1, 8, 6, 2, 4,6]
qsort2(unsortedArray, 0, len(unsortedArray) - 1)
unsortedArray

Out[2]:

[1, 2, 3, 4, 5, 6, 6, 6, 8]

Two-way partitioning 兩路分塊

選擇一個(gè)基準(zhǔn)元素放在開(kāi)頭确丢,在兩端開(kāi)始遍歷绷耍,當(dāng)l端找到大于基于元素的位置停下來(lái),當(dāng)r端找到不小于基準(zhǔn)元素的位置停下來(lái)鲜侥,兩者進(jìn)行交換褂始,直到兩者交叉或者相等,那么這個(gè)它r的位置就是基準(zhǔn)元素的位置

In [31]:

import random
def qsort3(alist,lower,upper):
    if(lower >= upper):
        return 
    idx = random.randint(lower,upper)
    alist[lower],alist[idx]=alist[idx],alist[lower]
    privot = alist[lower]
    left,right = lower+1,upper
    while left<=right:  # 等于的時(shí)候依然要繼續(xù)因?yàn)檫€沒(méi)劃定邊界描函,最后退出循環(huán)的時(shí)候一定是交叉的崎苗,r的右邊都是不小于基準(zhǔn)的,l的左邊都是小于基準(zhǔn)的
        while left <= right and alist[left]<privot:
            left+=1
        while right >=left and alist[right]>=privot:
            right-=1

        # 循環(huán)到這里要么是交叉了,要么是找到合適的位置了
        if left<right:
            alist[left],alist[right] = alist[right],alist[left]
            left+=1
            right-=1
        #print alist
    alist[lower],alist[right] = alist[right],alist[lower]
    qsort3(alist,lower,right-1)
    qsort3(alist,right+1,upper)

unsortedArray = [6, 5, 3,4, 1, 7,8, 7, 3,2, 4]
qsort3(unsortedArray, 0, len(unsortedArray) - 1)
unsortedArray

Out[31]:

[1, 2, 3, 3, 4, 4, 5, 6, 7, 7, 8]

隨機(jī)分區(qū)

如果待排序列正好是順序的時(shí)候舀寓,整個(gè)的遞歸將會(huì)達(dá)到最大遞歸深度(序列的長(zhǎng)度)胆数。而實(shí)際上在操作的時(shí)候,當(dāng)列表長(zhǎng)度大于1000(理論值)的時(shí)候互墓,程序會(huì)中斷必尼,報(bào)超出最大遞歸深度的錯(cuò)誤(maximum recursion depth exceeded)。在查過(guò)資料后我們知道篡撵,Python在默認(rèn)情況下判莉,最大遞歸深度為1000(理論值,其實(shí)真實(shí)情況下育谬,只有995左右骂租,各個(gè)系統(tǒng)這個(gè)值的大小也不同)。 這個(gè)問(wèn)題有兩種解決方案斑司, 1)重新設(shè)置最大遞歸深度,采用以下方法設(shè)置:

import sys

sys.setrecursionlimit(99999)

2)第二種方法就是采用另外一個(gè)版本的分區(qū)函數(shù),稱為隨機(jī)化分區(qū)函數(shù)宿刮。由于之前我們的選擇都是子序列的第一個(gè)數(shù)互站,因此對(duì)于特殊情況的健壯性就差了許多。現(xiàn)在我們隨機(jī)從子序列選擇基準(zhǔn)元素僵缺,這樣可以減少對(duì)特殊情況的差錯(cuò)率胡桃。

i = random.randint(p, r)

Heap Sort - 堆排序

堆排序的實(shí)現(xiàn)過(guò)程分為兩個(gè)子過(guò)程。第一步為取出大根堆的根節(jié)點(diǎn)(當(dāng)前堆的最大值), 由于取走了一個(gè)節(jié)點(diǎn)磕潮,故第二步需要對(duì)余下的元素重新建堆翠胰。重新建堆后繼續(xù)取根節(jié)點(diǎn),循環(huán)直至取完所有節(jié)點(diǎn)自脯,此時(shí)數(shù)組已經(jīng)有序之景。

堆的實(shí)現(xiàn)通過(guò)構(gòu)造二叉堆(binary heap),實(shí)為二叉樹(shù)的一種膏潮;由于其應(yīng)用的普遍性锻狗,當(dāng)不加限定時(shí),均指該數(shù)據(jù)結(jié)構(gòu)的這種實(shí)現(xiàn)焕参。這種數(shù)據(jù)結(jié)構(gòu)具有以下性質(zhì)轻纪。

  • 任意節(jié)點(diǎn)小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)叠纷。
  • 堆總是一棵完全樹(shù)刻帚。即除了最底層,其他層的節(jié)點(diǎn)都被元素填滿涩嚣,且最底層盡可能地從左到右填入崇众。

需要注意的是,堆是用數(shù)組保存的缓艳,所以根結(jié)點(diǎn)在下標(biāo)為0的位子校摩,又因?yàn)槎娑咽峭耆鏄?shù),所以下標(biāo)位n/2的地方是二叉樹(shù)里面最后一個(gè)非葉子結(jié)點(diǎn)的地方(有子結(jié)點(diǎn))阶淘,所以在建立大頂堆的時(shí)候衙吩,自底向上用下濾的方法建立各個(gè)小樹(shù),建每個(gè)小樹(shù)用時(shí)$log(i)$,共建了$\frac{n}{2} $個(gè)小樹(shù)

建立大頂堆有兩種方法 :

  1. 自底向上溪窒,先隨便把這些數(shù)據(jù)放在一個(gè)數(shù)組里面坤塞,然后從最深一層的節(jié)點(diǎn)開(kāi)始自底向上下濾操作
  2. 自頂向下,先建一個(gè)空的堆澈蚌,然后慢慢在最后位置插入新元素摹芙,并讓它向上濾

步驟:

  • 構(gòu)造最大堆(Build_Max_Heap):若數(shù)組下標(biāo)范圍為0~n,考慮到單獨(dú)一個(gè)元素是大根堆宛瞄,則從下標(biāo)n/2開(kāi)始的元素均為大根堆浮禾。于是只要從n/2-1開(kāi)始,向前依次構(gòu)造大根堆,這樣就能保證盈电,構(gòu)造到某個(gè)節(jié)點(diǎn)時(shí)蝴簇,它的左右子樹(shù)都已經(jīng)是大根堆。

  • 堆排序(HeapSort):由于堆是用數(shù)組模擬的匆帚。得到一個(gè)大根堆后熬词,數(shù)組內(nèi)部并不是有序的。因此需要將堆化數(shù)組有序化吸重。思想是移除根節(jié)點(diǎn)互拾,并做最大堆調(diào)整的遞歸運(yùn)算。第一次將heap[0]與heap[n-1]交換嚎幸,再對(duì)heap[0...n-2]做最大堆調(diào)整颜矿。第二次將heap[0]與heap[n-2]交換,再對(duì)heap[0...n-3]做最大堆調(diào)整鞭铆。重復(fù)該操作直至heap[0]和heap[1]交換或衡。由于每次都是將最大的數(shù)并入到后面的有序區(qū)間,故操作完后整個(gè)數(shù)組就是有序的了车遂。

  • 最大堆調(diào)整(Max_Heapify):該方法是提供給上述兩個(gè)過(guò)程調(diào)用的封断。目的是將堆的末端子節(jié)點(diǎn)作調(diào)整,使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn) 舶担。

最差時(shí)間復(fù)雜度 $O ( n log ? n )¥ 最優(yōu)時(shí)間復(fù)雜度$O ( n log ? n ) 平均時(shí)間復(fù)雜[$Θ ( n log ? n ) $

堆排在空間比較小(嵌入式設(shè)備和手機(jī))時(shí)特別有用坡疼,但是因?yàn)楝F(xiàn)代系統(tǒng)往往有較多的緩存,堆排序無(wú)法有效利用緩存衣陶,數(shù)組元素很少和相鄰的其他元素比較柄瑰,故緩存未命中的概率遠(yuǎn)大于其他在相鄰元素間比較的算法。但是在海量數(shù)據(jù)的排序下又重新發(fā)揮了重要作用剪况,因?yàn)樗诓迦氩僮骱蛣h除最大元素的混合動(dòng)態(tài)場(chǎng)景中能保證對(duì)數(shù)級(jí)別的運(yùn)行時(shí)間

In [17]:

def heap_sort(alist):
    # 下面是下濾的操作,下濾的前提是保證下面的子樹(shù)是已經(jīng)建好的子樹(shù) 
    def sink(alist,i,length):
        largest = i

        if (2*i+1)<length and alist[2*i+1]>alist[largest]:
            largest = 2*i+1
        if (2*i+2)<length and alist[2*i+2]>alist[largest]:
            largest = 2*i+2

        if largest != i:
            alist[largest],alist[i] = alist[i],alist[largest]
            sink(alist,largest,length)

    # 下面開(kāi)始堆排序的操作教沾,從最深一層的父節(jié)點(diǎn)開(kāi)始循環(huán),這樣可以保證下濾的時(shí)候译断,下面都是排好序的字節(jié)點(diǎn)

    # 先建立大頂堆 
    # n/2表示最后一個(gè)非葉結(jié)點(diǎn) 
    for i in xrange(len(alist)/2,-1,-1): #倒序到0授翻,所以第二位設(shè)置為-1
        sink(alist,i,len(alist))

    # 然后不斷底摘掉頂
    length = len(alist)
    for i in xrange(0,len(alist)):
        alist[0],alist[length-1] = alist[length-1],alist[0]
        length-=1
        sink(alist,0,length)

    return alist

unsortedArray = [6, 5, 3,13, 1, 8,28, 7, 2, 4]
sortedArray = heap_sort(unsortedArray)
sortedArray

Out[17]:

[1, 2, 3, 4, 5, 6, 7, 8, 13, 28]

堆排序在 top K 問(wèn)題中使用比較頻繁。堆排序是采用二叉堆的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的孙咪,雖然實(shí)質(zhì)上還是一維數(shù)組堪唐。二叉堆是一個(gè)近似完全二叉樹(shù) 。

堆排序解決Top K問(wèn)題

In [38]:

import heapq

heapq.nlargest(2,[9,5,12,38,32,21,1,-23])
heapq.nsmallest(2,[9,5,12,38,32,21,1,-23])

Out[38]:

[-23, 1]

[經(jīng)典排序算法][集錦]

對(duì)于比較排序算法翎蹈,我們知道淮菠,可以把所有可能出現(xiàn)的情況畫(huà)成二叉樹(shù)(決策樹(shù)模型),對(duì)于n個(gè)長(zhǎng)度的列表荤堪,其決策樹(shù)的高度為h合陵,葉子節(jié)點(diǎn)就是這個(gè)列表亂序的全部可能性為n!枢赔,而我們知道,這個(gè)二叉樹(shù)的葉子節(jié)點(diǎn)不會(huì)超過(guò)2h拥知,所以有2h>=n糠爬!,取對(duì)數(shù)举庶,可以知道,h>=logn!揩抡,這個(gè)是近似于O(nlogn)户侥。也就是說(shuō)比較排序算法的最好性能就是O(nlgn)。

那有沒(méi)有線性時(shí)間峦嗤,也就是時(shí)間復(fù)雜度為O(n)的算法呢蕊唐?答案是肯定的。不過(guò)由于排序在實(shí)際應(yīng)用中算法其實(shí)是非常復(fù)雜的烁设。這里只是討論在一些特殊情形下的線性排序算法替梨。特殊情形下的線性排序算法主要有計(jì)數(shù)排序,桶排序和基數(shù)排序装黑。這里只簡(jiǎn)單說(shuō)一下計(jì)數(shù)排序副瀑。

用Python實(shí)現(xiàn)常見(jiàn)排序算法


桶排序Bucket sort

經(jīng)典排序算法 - 桶排序Bucket sort

補(bǔ)充說(shuō)明三點(diǎn)

  1. 桶排序是穩(wěn)定的

  2. 桶排序是常見(jiàn)排序里最快的一種,比快排還要快…大多數(shù)情況下

  3. 桶排序非常快,但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法

但桶排序是有要求的恋谭,就是數(shù)組元素隸屬于固定(有限的)的區(qū)間,如范圍為[0-9] (考試分?jǐn)?shù)為1-100等),有時(shí)候想著感覺(jué)桶排序的第一步入桶操作和哈希表的構(gòu)造有點(diǎn)像呢

假設(shè)數(shù)據(jù)分布在[0糠睡,100)之間,每個(gè)桶內(nèi)部用鏈表表示疚颊,在數(shù)據(jù)入桶的同時(shí)插入排序狈孔。然后把各個(gè)桶中的數(shù)據(jù)合并。

In [20]:

import numpy as np

def bucket_sort(alist):
    # 下面是入桶的過(guò)程
    dic = dict()
    for item in alist:
        if item in dic:
            dic[item].append(item)
        else:
            dic[item]=[]
            dic[item].append(item)
    # 下面是歸并的過(guò)程

    result = []    
    for key,items in dic.items():
        for i in items:
            result.append(i)
    return result

unsortedArray = [6, 5, 3,5, 6, 5,3, 7, 3, 6]
sortedArray = bucket_sort(unsortedArray)
print sortedArray
[3, 3, 3, 5, 5, 5, 6, 6, 6, 7]

In [59]:

import heapq
def bucket_sort2(alist):
    # 下面是入桶的過(guò)程

    k = heapq.nlargest(1,alist)[0]+1
    dic = [None for i in range(k)]
    for item in alist:
        if dic[item]!=None:
            dic[item].append(item)
        else:
            dic[item]=[]
            dic[item].append(item)
    # 下面是歸并的過(guò)程

    result = []    
    for i in xrange(0,k):
        while dic[i]:
            result.append(dic[i].pop())
    return result

unsortedArray = [6, 5, 3,5, 6, 5,3, 7, 3, 6]
sortedArray = bucket_sort2(unsortedArray)
print sortedArray
[3, 3, 3, 5, 5, 5, 6, 6, 6, 7]

計(jì)數(shù)排序

計(jì)數(shù)排序是建立在對(duì)待排序列這樣的假設(shè)下:假設(shè)待排序列都是正整數(shù)(做下標(biāo)來(lái)用)材义。首先均抽,聲明一個(gè)新序列l(wèi)ist2,序列的長(zhǎng)度為待排序列中的最大數(shù)(可以通過(guò)建立大頂堆獲得)其掂。遍歷待排序列油挥,對(duì)每個(gè)數(shù),設(shè)其大小為i清寇,list2[i]++喘漏,這相當(dāng)于計(jì)數(shù)大小為i的數(shù)出現(xiàn)的次數(shù)。然后在依次加上前面的數(shù)华烟,就知道最終這個(gè)數(shù)應(yīng)該排在哪里了翩迈,然后,申請(qǐng)一個(gè)list盔夜,長(zhǎng)度等于待排序列的長(zhǎng)度(這個(gè)是輸出序列负饲,由此可以看出計(jì)數(shù)排序不是就地排序算法)堤魁,倒序遍歷待排序列(倒排的原因是為了保持排序的穩(wěn)定性,即大小相同的兩個(gè)數(shù)在排完序后位置不會(huì)調(diào)換)返十,假設(shè)當(dāng)前數(shù)大小為i妥泉,list[list2[i]-1] = i,同時(shí)list2[i]自減1(這是因?yàn)檫@個(gè)大小的數(shù)已經(jīng)輸出一個(gè)洞坑,所以大小要自減)盲链。于是,計(jì)數(shù)排序的源代碼如下迟杂。

In [48]:

import heapq
def count_sort(alist):

    k = heapq.nlargest(1,alist)[0]+1 ;# 算出alist中的最大數(shù)刽沾,解決Top k 問(wèn)題

    alist2 = [0 for i in range(k)] # 建立長(zhǎng)度為k初始化位0的數(shù)組
    alist3 = [0 for i in range(len(alist))] # 排序后的結(jié)果存在這里

    # 下面開(kāi)始計(jì)數(shù) 
    for item in alist:
        alist2[item]+=1

    # 下面開(kāi)始統(tǒng)計(jì)前面的,有點(diǎn)像積分操作 哈哈哈 算出來(lái)的就是最終的位置
    for i in range(1,k):
        alist2[i] += alist2[i-1]

    # 下面開(kāi)始倒序把數(shù)填在它該在的地方去
    for item in alist[::-1]: #倒序遍歷
        #print item
        alist3[alist2[item]-1] = item
        alist2[item]-=1
    return alist3

unsortedArray = [6, 5, 3,5, 6, 5,3, 7, 3, 6]
sortedArray = count_sort(unsortedArray)
print sortedArray    
[3, 3, 3, 5, 5, 5, 6, 6, 6, 7]

基數(shù)排序

流程

維基百科-基數(shù)排序

是一種非比較型整數(shù)排序算法排拷,其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字侧漓,然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串(比如名字或日期)和特定格式的浮點(diǎn)數(shù)监氢,所以基數(shù)排序也不是只能使用于整數(shù)布蔗。

它是這樣實(shí)現(xiàn)的:將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的數(shù)前面補(bǔ)零浪腐。然后纵揍,從最低位開(kāi)始,依次進(jìn)行一次排序牛欢。這樣從最低位排序一直到最高位排序完成以后骡男,數(shù)列就變成一個(gè)有序序列。

復(fù)雜度分析

基數(shù)排序的時(shí)間復(fù)雜度是O(k·n)傍睹,其中n是排序元素個(gè)數(shù)隔盛,k是數(shù)字位數(shù)。注意這不是說(shuō)這個(gè)時(shí)間復(fù)雜度一定優(yōu)于O(n·log(n))拾稳,k的大小取決于數(shù)字位的選擇(比如比特位數(shù))吮炕,和待排序數(shù)據(jù)所屬數(shù)據(jù)類型的全集的大小访得;k決定了進(jìn)行多少輪處理龙亲,而n是每輪處理的操作數(shù)目。

k約等于logB(N)

所以悍抑,基數(shù)排序的平均時(shí)間T就是:

T~= logB(N)·n

其中前一項(xiàng)是一個(gè)與輸入數(shù)據(jù)無(wú)關(guān)的常數(shù)鳄炉,當(dāng)然該項(xiàng)不一定小于logn

如果考慮和比較排序進(jìn)行對(duì)照,基數(shù)排序的形式復(fù)雜度雖然不一定更小搜骡,但由于不進(jìn)行比較拂盯,因此其基本操作的代價(jià)較小,而且在適當(dāng)選擇的B之下记靡,k一般不大于logn谈竿,所以基數(shù)排序一般要快過(guò)基于比較的排序团驱,比如快速排序。

例如

經(jīng)典排序算法 - 基數(shù)排序Radix sort

待排序數(shù)組[62,14,59,88,16]簡(jiǎn)單點(diǎn)五個(gè)數(shù)字

分配10個(gè)桶,桶編號(hào)為0-9,以個(gè)位數(shù)數(shù)字為桶編號(hào)依次入桶,變成下邊這樣

| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶編號(hào)

將桶里的數(shù)字順序取出來(lái),

輸出結(jié)果:[62,14,16,88,59]

再次入桶,不過(guò)這次以十位數(shù)的數(shù)字為準(zhǔn),進(jìn)入相應(yīng)的桶,變成下邊這樣:

由于前邊做了個(gè)位數(shù)的排序,所以當(dāng)十位數(shù)相等時(shí),個(gè)位數(shù)字是由小到大的順序入桶的,就是說(shuō),入完桶還是有序

| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶編號(hào)

因?yàn)闆](méi)有大過(guò)100的數(shù)字,沒(méi)有百位數(shù),所以到這排序完畢,順序取出即可

最后輸出結(jié)果:[14,16,59,62,88]

In [17]:

import math  # 求log和上約界

def radix_sort(alist,radix=10):
    # 首先計(jì)算入桶的次數(shù) 
    k = int( math.ceil(math.log(max(alist),radix)) )  # math.ceil返回的是整數(shù)

    # 然后每個(gè)數(shù)k次進(jìn)桶
    ## 首先定義一個(gè)可以接受list的桶的序列
    result = [ i for i in alist]
    bucket = [[] for i in range(radix) ]  # 按照基數(shù)大小確定桶的個(gè)數(shù)多少 
    for i in range(k):
        for item in result:  # 每次使用上次排完序的內(nèi)容
            # 求當(dāng)前位上應(yīng)該對(duì)應(yīng)的桶號(hào);
            ## 這里不必?fù)?dān)心位數(shù)多少的問(wèn)題,因?yàn)槲粩?shù)不夠下面求完就是0
            bucket[ item%(radix**(i+1))/(radix**i) ].append(item)

        # 然后合并各個(gè)桶
        del result[:]
        for small_bucket in bucket:
            result.extend(small_bucket)
        bucket = [[] for i in range(radix)]
    return result

unsortedArray = [26, 25, 23,5, 36, 5,3, 17, 3, 6,12,23,34,35,]
sortedArray = radix_sort(unsortedArray,10)
print sortedArray      
[3, 3, 5, 5, 6, 12, 17, 23, 23, 25, 26, 34, 35, 36]
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末空凸,一起剝皮案震驚了整個(gè)濱河市嚎花,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌呀洲,老刑警劉巖紊选,帶你破解...
    沈念sama閱讀 206,311評(píng)論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異道逗,居然都是意外死亡丛楚,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,339評(píng)論 2 382
  • 文/潘曉璐 我一進(jìn)店門憔辫,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人仿荆,你說(shuō)我怎么就攤上這事贰您。” “怎么了拢操?”我有些...
    開(kāi)封第一講書(shū)人閱讀 152,671評(píng)論 0 342
  • 文/不壞的土叔 我叫張陵锦亦,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我令境,道長(zhǎng)杠园,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 55,252評(píng)論 1 279
  • 正文 為了忘掉前任舔庶,我火速辦了婚禮抛蚁,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘惕橙。我一直安慰自己瞧甩,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,253評(píng)論 5 371
  • 文/花漫 我一把揭開(kāi)白布弥鹦。 她就那樣靜靜地躺著肚逸,像睡著了一般。 火紅的嫁衣襯著肌膚如雪彬坏。 梳的紋絲不亂的頭發(fā)上朦促,一...
    開(kāi)封第一講書(shū)人閱讀 49,031評(píng)論 1 285
  • 那天,我揣著相機(jī)與錄音栓始,去河邊找鬼务冕。 笑死,一個(gè)胖子當(dāng)著我的面吹牛混滔,可吹牛的內(nèi)容都是我干的洒疚。 我是一名探鬼主播歹颓,決...
    沈念sama閱讀 38,340評(píng)論 3 399
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼油湖!你這毒婦竟也來(lái)了巍扛?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 36,973評(píng)論 0 259
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤乏德,失蹤者是張志新(化名)和其女友劉穎撤奸,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體喊括,經(jīng)...
    沈念sama閱讀 43,466評(píng)論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡胧瓜,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,937評(píng)論 2 323
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了郑什。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片府喳。...
    茶點(diǎn)故事閱讀 38,039評(píng)論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖蘑拯,靈堂內(nèi)的尸體忽然破棺而出钝满,到底是詐尸還是另有隱情,我是刑警寧澤申窘,帶...
    沈念sama閱讀 33,701評(píng)論 4 323
  • 正文 年R本政府宣布弯蚜,位于F島的核電站,受9級(jí)特大地震影響剃法,放射性物質(zhì)發(fā)生泄漏碎捺。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,254評(píng)論 3 307
  • 文/蒙蒙 一贷洲、第九天 我趴在偏房一處隱蔽的房頂上張望收厨。 院中可真熱鬧,春花似錦优构、人聲如沸帽氓。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,259評(píng)論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)黎休。三九已至,卻和暖如春玉凯,著一層夾襖步出監(jiān)牢的瞬間势腮,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,485評(píng)論 1 262
  • 我被黑心中介騙來(lái)泰國(guó)打工漫仆, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留捎拯,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 45,497評(píng)論 2 354
  • 正文 我出身青樓盲厌,卻偏偏與公主長(zhǎng)得像署照,于是被迫代替她去往敵國(guó)和親祸泪。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,786評(píng)論 2 345

推薦閱讀更多精彩內(nèi)容