Catalog

[ Sort ]

Merge sort

Quick sort :

Insertion sort :

Bubble sort

Selection sort

Related exercises :

[ lookup ]

Two points search :

Fuzzy binary search :

Related exercises

[ Sort ]

Merge sort

# Merger
def mSort(nums): # It's divided into two lists , Sort them separately
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):# Merge two lists
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

Quick sort :

# Quick line up 、
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)# Low order
qSort(nums,pivot+1,high)# High order
def partition(nums,low,high):# Pivot point
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

Insertion sort :

# Insertion sort 、
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

Bubble sort

# Bubbling 、
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

Selection sort

# choice 、
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

Related exercises :

[ Maximum sliding window ]

Given an array  nums, There is a size of  k  The sliding window of the array moves from the leftmost side to the rightmost side of the array . You can only see in the sliding window  k  The number in . The sliding window moves only one bit to the right at a time . Return to the maximum sliding window .

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

[ lookup ]

Two points search :

# Two points search
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

Fuzzy binary search :

( Find the position of the first element in the array that is greater than or equal to the target element )

# Fuzzy dichotomy [ The position of the first element greater than or equal to the given value ]
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

Related exercises

[x The square root of ]

Calculate and return  x  The square root of , among  x  Is a nonnegative integer . Because the return type is an integer , The result only keeps the whole number part , The decimal part will be removed .

Method 1:

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

Method 2:

Newton method :https://en.wikipedia.org/wiki/Integer_square_root#Algorithm_using_Newton's_method

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)