Python 二分 排序 查找

[排序]

[查找]

# [排序]

## 归并排序

``````#归并
def mSort(nums): #分为两个列表，分别排序
if len(nums)<=1:
return nums
else:
m = len(nums)//2
print 'len(nums): ',len(nums)
print 'nums: ',nums
print 'm: ',m
left = mSort(nums[:m])
right = mSort(nums[m:])
ret = merge(left,right)
return ret
def merge(left,right):#合并两个列表
i = 0
j = 0
k = 0
ret =[]
print '--------'
print 'left: ',left
print 'right: ',right
while i<len(left) and j< len(right):
if left[i]<right[j]:
ret.append(left[i])
i += 1
else:
ret.append(right[j])
j += 1
ret += left[i:]
ret += right[j:]
return ret``````

## 快速排序:

``````#快排、
def quickSort(nums):
qSort(nums,0,len(nums)-1)
def qSort(nums,low,high):
if low<high:
pivot = partition(nums,low,high)
qSort(nums,low,pivot-1)#低位排序
qSort(nums,pivot+1,high)#高位排序
def partition(nums,low,high):#枢纽点
pivotkey = nums[low]
while low<high:
while low<high and nums[high]>=pivotkey:
high -= 1
nums[low],nums[high] = nums[high],nums[low]
while low<high and nums[low]<=pivotkey:
low += 1
nums[low],nums[high] = nums[high],nums[low]
return low``````

## 插入排序:

``````#插入排序、
def insertOrder(nums):
if not nums:
return
ret = [nums[0]]
for n in nums[1:]:
print 'for: ',n
print 'ret: ',ret
if n <= ret[0]:
ret.insert(0,n)
continue
i = 1
while i<len(ret):
if n>ret[i-1] and n<=ret[i]:
break
i+=1
ret.insert(i,n)
return ret``````

## 冒泡排序

``````#冒泡、
def paopao(nums):
flag = False
for i in range(len(nums)):
for j in range(len(nums)-1,i,-1):
if nums[j]<nums[j-1]:
flag = True
nums[j],nums[j-1] = nums[j-1],nums[j]
if not flag:
break
return nums``````

## 选择排序

``````#选择、
def selectOrder(nums):
for i in range(len(nums)):
minindex = len(nums)-1
for j in range(len(nums)-1,i-1,-1):
if nums[j]<nums[minindex]:
minindex = j
nums[i],nums[minindex] = nums[minindex],nums[i]
return nums``````

## 相关练习:

[滑动窗口最大值]

``````class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if nums==[] or k==1:
return nums
ret = []
now_max = max(nums[:k])
ret.append(now_max)
for i in range(1,len(nums)-k+1):
if nums[i+k-1] >= now_max:
now_max = nums[i+k-1]
elif nums[i-1]==now_max:
now_max = max(nums[i:i+k])
ret.append(now_max)
return ret``````

# [查找]

## 二分查找:

``````#二分查找
def halfSearch(nums,num):
if not nums:
return
if num>nums[-1] or num<nums[0]:
return
if num == nums[0]:
return 0
elif num == nums[-1]:
return len(nums)-1
low = 0
high = len(nums)-1
while low <= high:
medim = (high+low)/2
print 'm: ',medim
if num>nums[medim]:
low = medim+1
elif num < nums[medim]:
high = medim-1
else:
return medim
return``````

## 模糊二分查找:

(找到数组中大于等于目标元素的第一个元素的位置)

``````#模糊二分[大于等于给定值的第一个元素的位置]
def fuzzyHalfSearch(nums,num):
if not nums:
return
if num>nums[-1]:
return
if num <= nums[0]:
return 0
elif num == nums[-1]:
return len(nums)-1
low = 0
high = len(nums)-2
while low <= high:
medim = (high+low)/2
if num>nums[medim] and num<=nums[medim+1]:
return medim+1
elif num > nums[medim+1]:
low = medim+1
elif num <= nums[medim]:
high = medim
return``````

## 相关练习

[x 的平方根]

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x==0 or x==1:
return x
low =1
high = x-1
ans = 1
while low <= high:
medim = (low+high)/2
if x>medim*medim:
low = medim+1
ans = medim
elif x< medim*medim:
high = medim-1
else:
return medim
return ans``````

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x <= 1:
return x
r = x
while r > x / r:
r = (r + x / r) // 2
return int(r)``````

https://blog.csdn.net/m0_38019841/article/details/88235655