昨天滴滴二面，最后让我写个快排，突然发现连快排的操作流程都忘了，一度场面很尴尬，然后让我写一个atoi函数, 一下子也没有做到bug free。
还是基础不牢固啊，既然算法这件事避无可避的要伴随整个职业生涯，那就这次花时间把它们彻底搞懂。
突然又想起来当年校招面试WAP，一来就是直接在Ubuntu上写一个堆排序，然后我也木有写出来，真是捉急。以后不能这样了！
首先是快排。
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.quickSort(nums, 0, len(nums)-1)
return nums
def quickSort(self, nums, start, end):
if start >= end:
return
pivot = nums[start]
i = start + 1
j = end
while i <= j:
if nums[i] > pivot and nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
continue
if nums[i] <= pivot:
i += 1
if nums[j] >= pivot:
j -= 1
nums[start],nums[j] = nums[j], nums[start]
self.quickSort(nums, start, j-1)
self.quickSort(nums, j+1, end)
换了一种partition的方法：
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.quickSort(nums,0,len(nums)-1)
return nums
def quickSort(self,nums, left, right):
if left >= right:
return nums
mid = self.partition(nums, left, right)
self.quickSort(nums, left, mid-1)
self.quickSort(nums, mid+1, right)
return nums
def partition(self, nums, left, right):
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] < pivot:
nums[j], nums[i] = nums[i], nums[j]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
在改一种写法
def quick_sort(nums):
quickSort(nums, 0, len(nums) - 1)
return nums
def quickSort(nums, left, right):
if left > right:
return nums
mid = partition1(nums, left, right)
quickSort(nums, left, mid - 1)
quickSort(nums, mid + 1, right)
return nums
def partition(nums, left, right):
"""
常规的partition方法,利用两个指针，分别从左右两边向中间扫描
:param nums:
:param left:
:param right:
:return:
"""
pivot = nums[right]
i = left
j = right - 1
while i <= j:
if nums[i] > pivot and nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
continue
if nums[i] <= pivot:
i += 1
if nums[j] >= pivot:
j -= 1
nums[i], nums[right] = nums[right], nums[i]
return i
def partition1(nums, left, right):
"""
用i节点记录已经处理好的数组部分，只需要从左向右遍历一遍即可。
:param nums:
:param left:
:param right:
:return:
"""
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] < pivot:
nums[j], nums[i] = nums[i], nums[j]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
快速排序 非递归
主要是使用栈记录左右边界
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.quickSort(nums,0,len(nums)-1)
return nums
def quickSort(self,nums, left, right):
if left >= right:
return nums
stack = []
stack.append(right)
stack.append(left)
while len(stack):
left = stack.pop()
right = stack.pop()
mid = self.partition(nums, left, right)
if left < mid-1:
stack.append(mid-1)
stack.append(left)
if mid+1 < right:
stack.append(right)
stack.append(mid+1)
return nums
def partition(self, nums, left, right):
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] < pivot:
nums[j], nums[i] = nums[i], nums[j]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
归并排序
归并排序需要先分再合，需要重点关注的是merge函数，合并两个有序数组
def merge_sort(candidate):
if len(candidate) <= 1:
return candidate
mid = len(candidate) >> 1
candidate1 = merge_sort(candidate[:mid])
candidate2 = merge_sort(candidate[mid:])
result = merge(candidate1, candidate2)
return result
def merge(candidate1, candidate2):
result = []
i, j = 0, 0
while i < len(candidate1) and j < len(candidate2):
if candidate1[i] <= candidate2[j]:
result.append(candidate1[i])
i += 1
else:
result.append(candidate2[j])
j += 1
while i < len(candidate1):
result.append(candidate1[i])
i += 1
while j < len(candidate2):
result.append(candidate2[j])
j += 1
return result
冒泡排序
冒泡排序是一种稳定排序算法，每一次循环冒泡，将一个最值移动到最终的位置。
交换次数是核心开销，需要交换逆序度的次数。
def bubble_sort(candidate):
length = len(candidate)
flag = False
swap_cnt = 0
for i in range(length):
for j in range(length - i - 1):
if candidate[j] <= candidate[j + 1]:
continue
else:
swap_cnt += 1
candidate[j], candidate[j + 1] = candidate[j + 1], candidate[j]
flag = True
if not flag:
break
print('swap_cnt', swap_cnt)
return candidate
插入排序
插入排序的思想是：假定已经有一个已排序的数组，然后从第二个数开始，不断的往已排序数组中插入一个元素。
主要开销在于移动的次数，移动的次数也是逆序度。
def insert_sort(candidate):
length = len(candidate)
move_cnt = 0
for i in range(1, length):
tmp = candidate[i]
j = i - 1
while j >= 0 and candidate[j] > tmp:
candidate[j + 1] = candidate[j]
move_cnt += 1
j = j - 1
if j < i - 1:
candidate[j + 1] = tmp
print('move_cnt', move_cnt)
return candidate
选择排序
选择排序与插入排序思想有一点类似，也是假定已存在一个已排序数组，然后将未排序数组中的最小值插入到已排序数组中。
def select_sort(candidate):
length = len(candidate)
for i in range(length):
min_index = i
for j in range(i + 1, length):
if candidate[j] < candidate[min_index]:
min_index = j
candidate[i], candidate[min_index] = candidate[min_index], candidate[i]
return candidate
网友评论