前段時(shí)間在看計(jì)算機(jī)科學(xué)科學(xué)及編程導(dǎo)論，其中談到了排序的各種算法，在這我淺談四種插入，選擇，冒泡，以及堆排序。

首先需要知道算法是什么？

算法是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令程序的效率的一部分是由算法的時(shí)間復(fù)雜度或者是空間復(fù)雜度決定。這四種算法我用時(shí)間復(fù)雜度來(lái)分析

插入排序

插入排序一個(gè)經(jīng)典的列子整理?yè)淇伺啤Ｔ陂_(kāi)始摸牌時(shí)，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進(jìn)行比較。無(wú)論什么時(shí)候，左手中的牌都是排好序的。

偽代碼

list sort_insert(list):
       for i<-len(list) :
           for j <-i:
              if list[i]>list[j]:
                    Exchanging position
return list

代碼塊

def insert_sort(sort_list):
    for i in range(len(sort_list)):
        for j in range(i):
            if sort_list[i] > sort_list[j]:
                sort_list[j], sort_list[i] = sort_list[i], sort_list[j]
        print sort_list
    return sort_list

時(shí)間復(fù)雜度為o(n^2)

測(cè)試

sort_list = [8, 3, 4, 2, 6]
insert_sort(sort_list)
結(jié)果：
[8, 3, 4, 2, 6]
[8, 3, 4, 2, 6]
[8, 4, 3, 2, 6]
[8, 4, 3, 2, 6]
[8, 6, 4, 3, 2]

選擇排序

選擇排序是一種簡(jiǎn)單直觀的排序算法。工作原理，首先在未排序序列中找到最?。ù螅┰兀娣旁谂判蛐蛄械钠鹗嘉恢?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素

偽代碼

list select_sort(list):
     for i <-range(len(list):
          for j=i+1 <-range(len(list)):
               if list[j]<list[i]
                 Exchange postion

代碼

def select_sort(sort_list):
    for i in range(len(sort_list)):
        for j in range(i+1,len(sort_list)):
            if sort_list[j] < sort_list[i]:
                sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
        print sort_list
    return sort_list

時(shí)間復(fù)雜度為o(n^2)

測(cè)試

sort_list = [8, 3, 4, 56, 6, 1
select_sort(sort_list)
結(jié)果：
[1, 8, 4, 56, 6, 3]
[1, 3, 8, 56, 6, 4]
[1, 3, 4, 56, 8, 6]
[1, 3, 4, 6, 56, 8]
[1, 3, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]

3.冒泡排序

冒泡排序是臨近的數(shù)字兩兩進(jìn)行比較，按照從小到大或者從大到小的順序進(jìn)行交換

偽代碼

list bubble_list(list):
       for i<-len(list) :
           for j <-range(1,len(list)-i):
              if list[j-1]>list[j]:
                    Exchanging position
return list

代碼

def bubble_sort(sort_list):
    for i in range(len(sort_list)):
        for j in range(1,len(sort_list) - i):
            if sort_list[j] < sort_list[j-1]:
                sort_list[j-1], sort_list[j] = sort_list[j], sort_list[j-1]
        print sort_list
    return sort_list

時(shí)間復(fù)雜度為o(n^2)

測(cè)試

sort_list = [8, 3, 4, 56, 6, 1]
bubble_sort(sort_list)
結(jié)果：

[3, 4, 8, 6, 1, 56]
[3, 4, 6, 1, 8, 56]
[3, 4, 1, 6, 8, 56]
[3, 1, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]
[1, 3, 4, 6, 8, 56]

4.堆排序

堆排序利用了堆這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序算法，分了小堆和大堆，滿足子節(jié)點(diǎn)總是小于父節(jié)點(diǎn)

    # 創(chuàng)建最大堆
    for start in range((len(list) - 2) // 2, -1, -1):
        sift_down(list, start, len(list) - 1)
    # 堆排序
    for end in range(len(list) - 1, 0, -1):
        list[0], list[end] = list[end], list[0]
        sift_down(list, 0, end - 1)
    return list
#最大堆調(diào)整
def sift_down(lst, start, end):
    root = start
    while True:
        child = 2 * root + 1
        if child > end:
            break
        if child + 1 <= end and lst[child] < lst[child + 1]:
            child += 1
        if lst[root] < lst[child]:
            lst[root], lst[child] = lst[child], lst[root]
            root = child
        else:
            break

時(shí)間復(fù)雜度為n*log2n
??百萬(wàn)級(jí)數(shù)據(jù)上堆排序是相對(duì)于其他三個(gè)排序更加適合，插入一般不用在數(shù)量超過(guò)一千的場(chǎng)合下，插入的最好時(shí)間復(fù)雜度為o(n) 最差為o(n^2) ，而冒泡和選擇是對(duì)數(shù)級(jí)增長(zhǎng)，一般并不推薦使用