??偶然間發(fā)現(xiàn)了自己以前寫的十種排序算法的代碼折欠，現(xiàn)粘貼上來醇蝴，方便自己日后查閱~ （里面還附贈了和
的實現(xiàn)方法）
- 目錄：
算法：附錄
算法（1）：遞歸
算法（2）：鏈表
算法（3）：數(shù)組
算法（4）：字符串
算法（5）：二叉樹
算法（6）：二叉查找樹
算法（7）：隊列和堆棧（附贈BFS和DFS）
算法（8）：動態(tài)規(guī)劃
算法（9）：哈希表
算法（10）：排序
算法（11）：回溯法
算法（12）：位操作
小伙子我心腸好诈火，再送倆非遞歸實現(xiàn)~
#python3
'''
插入排序：插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中昼钻，從而得到一個新的魔种、個數(shù)加一的有序數(shù)據(jù)析二，
算法適用于少量數(shù)據(jù)的排序；首先將第一個作為已經(jīng)排好序的节预，然后每次從后的取出插入到前面并排序叶摄；
'''
def insert_sort(ilist):
for i in range(len(ilist)):
for j in range(i):
if ilist[i] < ilist[j]:
# ilist[i], ilist[j] = ilist[j], ilist[i]
ilist.insert(j, ilist.pop(i))
break
return ilist
'''
希爾排序是第一個突破O(n^2)的排序算法；是簡單插入排序的改進版安拟；是把記錄按下標(biāo)的一定增量分組蛤吓，
對每組使用直接插入排序算法排序；隨著增量逐漸減少糠赦，每組包含的關(guān)鍵詞越來越多会傲，當(dāng)增量減至1時，
整個文件恰被分成一組拙泽，算法便終止
'''
def shell_sort(ilist):
gap=len(ilist)
while gap>1:
gap=gap//2
for i in range(gap,len(ilist)):
for j in range(i%gap,i,gap):
if ilist[i]<ilist[j]:
ilist[i],ilist[j]=ilist[j],ilist[i]
return ilist
'''
冒泡排序：它重復(fù)地走訪過要排序的數(shù)列淌山，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來顾瞻。
走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換泼疑，也就是說該數(shù)列已經(jīng)排序完成
'''
def bubble_sort(ilist):
flag=len(ilist)-1
for i in range(len(ilist)):
for j in range(flag):
if ilist[j]>ilist[j+1]:
flag=j
ilist[j], ilist[j+1] = ilist[j+1], ilist[j]
return ilist
'''
快速排序：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小荷荤，
然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序退渗，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列
'''
def quick_sort(ilist):
if ilist==[]:
return []
qfirst=ilist[0]
qsmall=quick_sort([s for s in ilist[1:] if s < qfirst])
qlarge=quick_sort([l for l in ilist[1:] if l >=qfirst])
return qsmall +[qfirst] +qlarge
'''
選擇排序：第1趟梅猿，在待排序記錄r1 ~ r[n]中選出最小的記錄氓辣，將它與r1交換；第2趟袱蚓，在待排序記錄r2 ~ r[n]中選出最小的記錄，
將它與r2交換几蜻；以此類推喇潘，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄体斩，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢
'''
def select_sort(ilist):
for i in range(len(ilist)):
a=i
for j in range(i+1,len(ilist)):
if ilist[j]<ilist[a]:
a=j
ilist[i],ilist[a]=ilist[a],ilist[i]
return ilist
'''
歸并排序：采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用颖低。將已有序的子序列合并絮吵，得到完全有序的序列；
即先使每個子序列有序忱屑，再使子序列段間有序蹬敲。若將兩個有序表合并成一個有序表，稱為二路歸并
'''
def merge_sort(ilist):
def recursive(ilist):
if len(ilist)==1:
return ilist
mid=len(ilist)//2
left=recursive(ilist[:mid])
right=recursive(ilist[mid:])
return merge(left,right)
def merge(left,right):
ans=[]
while len(left) and len(right):
if left[0]<= right[0]:
ans.append(left.pop(0))
else:
ans.append(right.pop(0))
ans.extend(left)
ans.extend(right)
return ans
return recursive(ilist)
'''
基數(shù)排序是按照低位先排序莺戒，然后收集伴嗡；再按照高位排序，然后再收集从铲；依次類推瘪校，直到最高位。有時候有些屬性是有優(yōu)先級順序的名段，
先按低優(yōu)先級排序阱扬，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前伸辟，高優(yōu)先級相同的低優(yōu)先級高的在前麻惶。
基數(shù)排序基于分別排序，分別收集信夫，所以是穩(wěn)定的用踩。
'''
def radix_sort(ilist):
bucket,digit=[[]],0
while len(bucket[0])!=len(ilist):
bucket=[[] for x in range(10)]
for i in ilist:
num=(i//10**digit)%10
bucket[num].append(i)
ilist=[a for b in bucket for a in b]
digit+=1
return ilist
'''
計數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法。計數(shù)排序使用一個額外的數(shù)組C忙迁，其中第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)脐彩。
然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對整數(shù)進行排序姊扔。
'''
def counting_sort(ilist):
n = len(ilist)
b = [0 for i in range(n)]
c = [0 for i in range(max(ilist)+1)]
for j in ilist:
c[j] = c[j] + 1
for i in range(1, len(c)):
c[i] = c[i] + c[i-1]
for j in ilist:
b[c[j] - 1] = j
c[j] = c[j] - 1
return b
'''
桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布惠奸，將數(shù)據(jù)分到有限數(shù)量的桶里，每個桶再分別排序
（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序)
桶劃分的越小恰梢，各個桶之間的數(shù)據(jù)越少佛南，排序所用的時間也會越少。但相應(yīng)的空間消耗就會增大嵌言。
該例子中嗅回，設(shè)置桶的數(shù)量為(max(ilist) - min(ilist)) + 1），跟計數(shù)排序很像
'''
def bucket_sort(ilist):
buckets = [0] * ((max(ilist) - min(ilist)) + 1) # 初始化桶元素為0
for i in range(len(ilist)):
buckets[ilist[i] - min(ilist)] += 1 # 遍歷數(shù)組a摧茴，在桶的相應(yīng)位置累加值
b = []
for i in range(len(buckets)):
if buckets[i] != 0:
b += [i + min(ilist)] * buckets[i]
return b
'''
堆排序：它是選擇排序的一種绵载。可以利用數(shù)組的特點快速定位指定索引的元素。堆分為大根堆和小根堆娃豹，是完全二叉樹焚虱。
大根堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值，即A[PARENT[i]] >= A[i]懂版。在數(shù)組的非降序排序中鹃栽，
需要使用的就是大根堆，因為根據(jù)大根堆的要求可知躯畴，最大的值一定在堆頂
lchild=parent*2+1 rchild=parent*2+2
'''
def heap_sort(ilist):
def heap_adjust(parent):
child=parent*2+1
while child<len(heap):
if child +1<len(heap):
if heap[child +1]>heap[child]:
child=child+1
if heap[parent]>=heap[child]:
break
heap[parent],heap[child]=heap[child],heap[parent]
parent, child = child, 2 * child + 1
heap, ilist = ilist.copy(), []
for i in range(len(heap)//2,-1,-1):
heap_adjust(i)
while len(heap)!=0:
heap[0],heap[-1]=heap[-1],heap[0]
ilist.insert(0,heap.pop())
heap_adjust(0)
return ilist
#Ann = n!
def Ann(arr):
def first(ans,arr):
if len(arr)==0:
return print(ans)
arr_t=arr.copy()
num=arr_t.pop(0)
for i in range(len(ans)+1):
temp=ans.copy()
temp.insert(i,num)
first(temp,arr_t)
return first([],arr)
#Anm = n! / (n-m)!
#Cnm = n! / ( m! * (n-m)! )
def Cnm(lis,m,start=0):
if m==0:
for i in range(start-1):
if lis[i]>lis[i+1]: # 只取從小到大的那種排列方式民鼓，去掉這句就是Anm的實現(xiàn)
break
else:
print(lis[:start])
global count
count += 1
return 0
for i in range(start,len(lis)):
lis[start],lis[i]=lis[i],lis[start]
Cnm(lis,m-1,start+1)
lis[start], lis[i] = lis[i], lis[start]
if __name__=="__main__":
# Ann(['a', 'b', 'c', 'd', 'e'])
ilist=[4,5,6,7,3,2,6,9,8]
print(bubble_sort(ilist))
