折半查找
def bisearch(a,x,low,high):
while low<=high:
mid=(low+high)//2
print('當前mid值：',mid)
if a[mid]==x:
return mid
elif a[mid]<x:
low=mid+1
else:
high=mid-1
return 0
復雜度分析：
設查找次數(shù)為k
要查找的數(shù)組長度為：n,n/2,n/4,n/2k..直到n/2k等于1嫉鲸，此時解出k=log2n
時間復雜度為O(n)=log2n
**大O表示法：‘長遠主流’
選擇排序
version1：出錯的版本
def choose_sort(arr):
for i in range(len(arr)):
temp=arr[i]
k=i
for j in range(i+1,len(arr)):
if temp>arr[j]:
temp=arr[j]
k=j
if arr[i]<temp:#由于temp的有效范圍灭衷，此時的temp為外層for下面的temp杂瘸，并非在內層for中修改后的temp，所以這個算法在c中是對的碉咆，在python中要修改
temp=arr[i]
arr[i]=arr[k]
arr[k]=temp
version2:改進部分：每一次比較都做一次交換抖韩，使得arr[smallest]保持為最小的值
def choose_sort2(arr):
for i in range(len(arr)):
smallest=i#保存最小值的坐標
for j in range(i+1,len(arr)):
if arr[smallest]>arr[j]:
temp=arr[smallest]
arr[smallest]=arr[j]
arr[j]=temp
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
快速排序（分治思想）
分區(qū)函數(shù)
def partion(arr,low,high):
i,j=low,high
temp=arr[i]#取第一個數(shù)為基準值
while i<j:#當i==j時，說明此時已經(jīng)找到了基于基準值的分解點疫铜。
while arr[j]>temp & i<j:
j-=1
if i>=j:#此處為第一次糾錯點
break
arr[i]=arr[j]
i+=1
while (arr[i]<temp) & (i<j):#代碼糾錯：原因是&運算符的優(yōu)先級過高茂浮。
i+=1
if i>=j:
break
arr[j]=arr[i]
j-=1
arr[i]=temp
return i
def quicksort(arr,low,high):
if low<high:
x=partion(arr,low,high)
quicksort(arr,low,x-1)
quicksort(arr,x+1,high)
關于一個算法的運行時間，通晨樵埽考量兩點：
1励稳，大O表示法的時間復雜度
2，基本操作的時間常量C
對于O(n)相同的兩種算法囱井，再考量時間常量C
比如歸并算法和快速排序算法驹尼。平均時間復雜度都是O(nlog2n)，但快速排序的時間常量C要小得多庞呕，因此快速排序大多數(shù)情況下更快新翎。
