【Python】基本的搜索與排序演算法

1、基本搜索演算法

（1）最小值搜索

（2）順序搜索

（3）二分搜索

2、基本排序演算法

（1）選擇

（2）冒泡

（3）插入

3、更快的排序演算法

演算法複雜度從n的平方階到nlog(n)

（1）快速排序

（2）選擇排序

以下是Python代碼：

1、基本搜索

（1）最小值搜索-沒辦法，必須遍歷所有元素，所以是固定的線性時間複雜度

"""返回最小項的index。思路：默認第一個最小，再一次比較Python有內置函數min，這裡我們自己實現它"""def IndexOfMin(lst): min=0 #用for和while都行 # for i in range(1,len(lst)): # if (lst[i]<lst[min]): # min=i current_index=1 while current_index<len(lst): if(lst[current_index]<lst[min]): min=current_index current_index+=1 return mina_lst=[6,5,4,3,1,5]min=IndexOfMin(a_lst)print(min)"""用到了兩個變數：min和current_index這個演算法的複雜度是O(n)，列表大小為n，比較n-1次。n-1是確定的，必須從頭到尾"""

（2）順序搜索-找到了就可以break，不用遍歷所有，所以複雜度要分最好最壞

"""順序搜索-針對無序列表，如果是有序的，可以二分法提高效率Python有內建的in，這裡我們自己實現它默認返回-1，找到更改(好幾次忘記寫i++，陷入死循環……注意了！）def SequentialSearch(target,lst): #for 和while都可以，但我盡量不用for 吧 position=-1 i=0 while i<len(lst): if lst[i]==target: position=i i+=1 return positiona_target=6lst1=[1,2,3,4]lst2=[1,2,6,4]position1=SequentialSearch(a_target,lst1)position2=SequentialSearch(a_target,lst2)print(position1)#-1print(position2)#2我這裡函數內定義了兩個變數，i和position，書上只用了1個他是如何做到的？position=0開始，如果遇到就立即返回；搜索到最後還沒有，才返回-1.確實高明很多，而且我寫的邏輯不對：都找到了幹嘛還繼續找啊？"""def SequentialSearch(target,lst): #for 和while都可以，但我盡量不用for 吧 position=0 while position<len(lst): if lst[position]==target: return position position+=1#這麼多年第一次體會到+=寫法的好處…… return -1a_target=6lst1=[1,2,3,4]lst2=[1,2,6,4]position1=SequentialSearch(a_target,lst1)position2=SequentialSearch(a_target,lst2)print(position1)#-1print(position2)#2"""這個演算法的複雜度就不一定了for循環中隨時可以返回最好情況，一次返回O（1）最壞情況，n次返回O（n)平均：可能出現的所有情況是：1次找到，2次找到，3次找到……n次找到所以平均是（1+2+……+n)/n=(1+n)/2=0.5+0.5n，還是n的線性關係，O（n）"""

（3）二分搜索-對有序列表，用二分搜索比順序效率高，複雜度：log2（n）

"""對有序列表，用二叉搜索可以提高效率"""def binarySearch(target,sorted_lst): #mid=int(len(sorted_lst)/2)這裡不要用長度來算mid，因為要保留index #這裡不用遞歸 left=0 right=len(sorted_lst)-1#開兩個指針，分別指向第一個元素和最後一個元素 while left<=right:#有等號，等於的時候還需要比較，有交叉跨越才結束 mid = (left + right) //2#//表示整除 if target==sorted_lst[mid]: return mid if target>sorted_lst[mid]: left=mid+1 elif target<sorted_lst[mid]: right=mid-1 return -1sorted_lst1=[1,2,3,4,5,6,7,8]sorted_lst2=[]position1=binarySearch(7,sorted_lst1)#6position2=binarySearch(0,sorted_lst1)#-1position3=binarySearch(0,sorted_lst2)#-1print(position1)print(position2)print(position3)"""複雜度：log2（n）最好：1輪最差：第一輪n/2,第二輪再/2，第三輪再/2……一直到結果為1.（嚴格說結果為1以後，還有一輪比較：在得到結果為1這一輪代表著還剩下2個或3個元素，本輪比較可以排除1個元素，那麼剩下1或2個元素是不是target還需要下一輪n除以2的k次方=1，那麼n=2的k次方，k=log2（n），實際的次數是log2(n)+1，不過在複雜度這裡+1就省略了吧。當n趨近於無窮大的時候，常數算不了什麼的"""

2、基本排序

（1）選擇

"""選擇排序：選擇-交換-再選擇-再交換……每一輪（1）選擇最小的項（2）放到最前面（3）看條件是否進入下一輪"""def swap(lst,i,j): temp=lst[j] lst[j]=lst[i] lst[i]=tempdef selectionSort(lst): i=0 while i<len(lst)-1:##這裡只需要保證i=len(lst)-2，即倒數第二個元素是最小就可以結束了 外層每一輪目標：選出本輪最小，並交換， min=i j=i+1 while(j<len(lst)):#內存循環結束選出本輪最小 if lst[j]<lst[min]: min=j j+=1 swap(lst,i,min) i+=1"""【差別】1、我的外層循環進行了len(lst)次，書上最後一次不用？因為在進行了len(lst)-1此排序後，已經可以保證坐標為len(lst)-2的值比len(lst)-1的值要小，不需要再比較了2、書上是先判斷min和i不相等再swap，多了一次判斷，但如果相等就節約了swap運算，不知道哪種效率高？"""lst=[3,5,6,2,3,7]selectionSort(lst)print(lst)""""開銷：外層循環n-1次，內層循環視i而定(n-1)+(n-2)+……+1=n(n-1)/2,所以主要開銷的複雜度是【n的平方】另外有額外的swap的開銷，最多n-1次，最少0次，平均是線性的"""

（2）冒泡與改進的冒泡（如果第一輪冒泡全程未發生交換，則不用進入下一輪了→最好情況下時間複雜度提高到線性）

"""冒泡演算法每一輪：通過兩兩比較將最大值排到最後"""def swap(lst,i,j): temp=lst[j] lst[j]=lst[i] lst[i]=tempdef bubbleSort(lst): i=len(lst)-1 while (i>0): j=0 while(j<i): if lst[j]>lst[j+1]: swap(lst,i,j) j+=1 i-=1lst=[3,5,6,2,3,7]bubbleSort(lst)print(lst)"""複雜度：外層循環n-1輪，第一輪保證下標n-1是最大，第2輪保證n-2輪最大，第n-1輪保證下標1最大內層循環的輪數不同，j從0開始，到i-1結束所以總共是(n-1)+(n-2)+……+1=（n-1）n/2主要開銷還是n的平方，額外swap開銷最小0次，最壞情況下，也會是n的平方……""""""改進：上述演算法還有可以改進的地方！假如第一輪冒泡全程沒有發生交換，說明列表順序已經排列好，就不需要進行下一輪了於是可以改進如下：不過這種改進也只能改進較好情況下的效率，如果最好最好，第1輪循環後就排好不用再繼續的話，複雜度就是線性階……不過在大多數普通情況下仍然是n的平房"""def swap(lst, i, j): temp = lst[j] lst[j] = lst[i] lst[i] = tempdef bubbleSort(lst): i = len(lst) - 1 while (i > 0): swapped=False#每一輪加一個標誌位，用於標誌毛包過程中是否發生了交換 j = 0 while (j < i): if lst[j] > lst[j + 1]: swap(lst, i, j) swapped=True j += 1 if (swapped==False): return i -= 1lst = [3, 5, 6, 2, 3, 7]bubbleSort(lst)print(lst)

（3）插入（寫起來略複雜，不過最好情況可以到達線性）

"""每一輪保證前面的都已排序，然後把其後的一個插入到合適的位置即可寫起來稍微複雜"""def insertSort(lst): i=0 while(i<len(lst)-1):#在這一輪要把第i+1個插入0-i的有序隊列中 j=0 while j<=i: if(lst[i+1]<lst[j]):#找到插入點，把lst[i+1]放在j的位置，然後把原j到i的順移到j+1到i+1 temp=lst[i+1] k = i while (k>=j): lst[k+1]=lst[k] k-=1 lst[j]=temp j+=1 #print(i,lst) i+=1lst = [3, 5,4, 6,9, 2, 3, 7]insertSort(lst)print(lst)"""比較書上的寫法，比我高明太多。我是將帶插入的元素依次與前面的元素從前到後比較，一旦插入元素小於當前元素（能來到這裡自然默認地大於前一個元素），插入位置就確定下來後，最後的插入通過"三角"倒換來實現。而書上是：從後到前的比較，一旦插入元素小於當前元素，插入具體位置還不能確定（還要看是否大於前一個元素），看可以確定插入位置肯定是當前或者再往前，於是可以把當前元素往後挪一位。由於從後開始，不用擔心後面一位的值被覆蓋，因此在此之前已經被挪走了。"""def insertSort(lst): i=0 while(i<len(lst)-1):#在這一輪要把第i+1個插入0-i的有序隊列中 j=i temp = lst[i + 1]#必須把第i+1個元素的值保存出來，否則每次滿足if就會被覆蓋 while j>=0: if(temp<lst[j]):#找到插入點，把lst[i+1]放在j的位置，然後把原j到i的順移到j+1到i+1 lst[j+1]=lst[j] j-=1 else: break #至此插入點才確定 lst[j+1]=temp i+=1lst = [3, 5,4, 6,9, 2, 3, 7]insertSort(lst)print(lst)""""有點麻煩，改了一會兒才改對複雜度：外層n-1輪循環，內層要看情況如果最壞，所有數據未排序，那麼是1+2+……+（n-1),複雜度是n的平方如果最好，所有數據已排序，內層循環的第一輪就會執行else break，也就是內層只執行1輪，一共就是外層的n-1次循環，所以總體是線性的。如果是普通情況，複雜度介於兩者之間，仍然是n的平方次階"""

3、更快的排序演算法

（1）快速排序

"""快速排序：（1）隨機選取一個基準點，並與最後一項交換（2）通過遍歷前面n-1個元素，把小於基準點的元素全部放到最前面，然後列表分割成兩半（3）對子列表繼續重複複雜度分析：每一輪分割以後，對子列表除基準點以外的所有元素都要進行遍歷，所以合起來近似是n（近似是因為這裡沒有減去基準點）所以關鍵在於分割多少輪最好的情況下，每次都恰好選擇不大不小中間的那個數，使得列表長度減半。類似二分，這種情況下經過log2（n）次分割，就會結束。撐起來是n*log2（n）但最差情況下，假如你選取的基準恰好是最小或最大的那個數，那麼就要分（n-1）次。乘起來是n*(n-1)兩者差別很大"""def swap(lst,i,j): temp=lst[j] lst[j]=lst[i] lst[i]=tempdef partition(lst,left,right): pivot_index = (left + right) // 2 pivot = lst[pivot_index] swap(lst, pivot_index, right) # 開始把小的排左邊，大的排右邊 i=left position = left while (i < right): # 沒有=是因為right已經是基準值了 if lst[position] < pivot: # 如果找到一個，就放開頭去，然後從下一個開始掃描 swap(lst, position, position) position += 1 i+=1 swap(lst, i, right) return positiondef divide(lst,left,right): if (left<right): dv=partition2(lst,left,right) divide(lst,left,dv-1) divide(lst,dv+1,right)def fast_sort(lst): left=0 right=len(lst)-1 divide2(lst,left,right)lst=[]for count in range(20): lst.append(random.randint(1,100))print(raw lst:,lst)fast_sort(lst)print(after fast sort:,lst)

（2）選擇排序

"""合併排序：（1）數組對半分成2個，再分成4個……一直到只有1個 從上到下（2）對最小的列表排序 在最下（3）合併 從下到上寫起來有點困難，主要是各個功能怎麼配合。具體是兩個子列表怎麼按有序的方式合併：開第三個列表作為結果列表，然後兩個指針，分別指向兩個子列表的開頭，兩者相比值較小的放進結果列表，然後指針後移"""#一個思路：像這種不知道要拆分多少次的適合用遞歸而不是循環#明確：在一個遞歸里完成的事情是，當前列表拆分成2個與這2個列表的合併def mergeSort(lst): left=0 right=len(lst)-1 copyBuffer = list(range(len(lst)))#必須提前指定大小，否則不能直接對下標為index的元素賦值 if (left < right): divide(lst,left,right, copyBuffer)def divide(lst,left, right, copyBuffer): if (left<right):#如果列表不止1個元素，就拆成兩個列表，然後以排序的方式合併 mid=(left+right)//2 divide(lst,left,mid,copyBuffer) divide(lst,mid+1,right,copyBuffer) merge(lst,left,mid,right,copyBuffer)def merge(lst,left,mid,right,copyBuffer): #兩個子列表lst[left：mid+1]和[mid+1：right+1] l1=left l2=mid+1 i=left while (i<right+1):#填滿下標為left-right的元素 if (l1>mid):#l1 exausted copyBuffer[i]=lst[l2] l2+=1 elif (l2>right):#l2 exausted copyBuffer[i]=lst[l1] l1+=1 elif (lst[l1]<lst[l2]): copyBuffer[i]=lst[l1] l1+=1 else: copyBuffer[i]=lst[l2] l2+=1 i+=1 for i in range(left,right+1): lst[i]=copyBuffer[i]#測試import randomlst=[]for count in range(20): lst.append(random.randint(1,100))print(raw lst:,lst)mergeSort(lst)print(after fast sort:,lst)"""複雜度分析：n*log（n）？"""

4、Fibonacci的實現（遞歸的指數級演算法）→（基於循環的線性演算法）

（1）遞歸的指數級演算法

"""遞歸實現Fibonacci，形式簡單，但是時間複雜度是指數階1、1、2、3、5、8、13、21、34"""def fib(n): if n>2: return fib(n-1)+fib(n-2) else :#fib(1)=fib(2)=2 return 1print(fib(1))#1print(fib(2))#1print(fib(3))#2print(fib(4))#3print(fib(5))#5print(fib(6))#8"""複雜度：假設是滿滿的平衡樹1-2-4-8……，總共調用次數是2+4+8+2^n，合起來是2^(n+1)-2，雖然調用樹是不平衡的，但其形狀接近平衡樹，因此也會很近似指數階用循環來寫，解除遞歸"""

（2）基於循環的線性演算法

"""為了使複雜度降低至線性，用循環來解除遞歸"""def fib(n): i=1 last_one=1 last_two=1 while (i<=n): if i==1: current=1 elif i==2: current=1 else: current=last_one+last_two last_two=last_one last_one=current i+=1 return currentprint(fib(1))#1print(fib(2))#1print(fib(3))#2print(fib(4))#3print(fib(5))#5print(fib(6))#8

4、另外補一個：如何實現類的實例可比較？

通過重寫類的__lt__,__gt__，__eq__方法，在方法中指定比較規則，實現類的實例也可以用=<>來比較』

"""最小查找、順序查找、二分查找，都是通過多次比較來查找。後面的排序，排序的依據也是基於比較。關於【比較】通過重寫類的__lt__,__gt__，__eq__方法，在方法中指定比較規則，實現類的實例也可以用=<>來比較"""class Count(object): def __init__(self,name,salary): self._name=name self._salary=salary def __lt__(self,another): return self._salary<another._salary def __gt__(self,another): return self._salary>another._salary def __eq__(self,another): return self._salary==another._salarya=Count(tian,500)b=Count(wei,1000)c=Count(tt,500)print(a<b)#Trueprint(a>b)#Falseprint(a==b)#Falseprint(a==c)#True

0302 今早複習時踩到的坑

1、循環的末尾忘了i+=1

2、二分搜索：只能對有序序列排序。

可以用遞歸實現，也可以拆成循環：把遞歸調用的函數實現變成循環體，遞歸的結束條件的否定作為判斷循環是否繼續的依據。

（1）遞歸實現

def binarySearch(target,lst): left=0 right=len(lst)-1 if left<right: return search(target, left, right,lst)def search(target, left, right,lst): print(left,right) if left>right: return -1 mid=(left+right)//2 if target==lst[mid]: return mid elif target>lst[mid]: return search(target,mid+1,right,lst) else: return search(target,left,mid-1,lst)lst=[1,2,3,4,5,6]result=binarySearch(7,lst)print(result)

（2）循環實現

def binarySearch(target,lst): left=0 right=len(lst)-1 while left<=right:#注意有等號，相等的時候依然需要比較 mid=(left+right)//2 if target==lst[mid]: return mid elif target>lst[mid]: left=mid+1 else: right=mid-1 return -1lst=[1,2,3,4,5,6]result=binarySearch(1,lst)print(result)

推薦閱讀：