数据结构与算法-排序/二分查找
算法中基础中的基础，排序/二分查找 排序 1.快排QuickSort
def quicksort(nums):
return QS(nums,0,len(nums)-1)def QS(nums,left,right):
if left >= right:
return nums
key = nums[left]
lp = left
rp = right
while lp < rp:
while nums[rp] >= key and lp归并排序
def merge_sort(lst):
if len(lst) <=1:
return lst
else:
middle = len(lst)//2
left = lst[:middle]
right = lst[middle:]
merge_sort(left)
merge_sort(right)
i,j,k = 0,0,0
while i < len(left) and j< len(right):
if left[i] <= right[j]:
lst[k] = left[i]
i = i + 1
else:
lst[k] = right[j]
j = j + 1
k = k + 1
while i < len(left):
lst[k] = left[i]
i += 1
k += 1
while j < len(right):
lst[k] = right[j]
j += 1
k += 1
return lst
堆排序
def shiftdown(lst,i,n):
h = 2 * i + 1
while h <= n:
if h + 1 <= n and lst[h+1] > lst[h]:
h = h + 1
if lst[h] > lst[i]:
lst[i],lst[h] = lst[h],lst[i]
else:
break
i = h
h = 2 * i + 1def heapSort(lst):
length = len(lst)
for j in range(length//2 - 1,-1,-1):
shiftdown(lst,j,length-1)
print('lst_tmp',lst)
for i in range(length-1,0,-1):
lst[0],lst[i] = lst[i],lst[0]
shiftdown(lst,0,i-1)
print('sorted lst',lst)
1. 二分查找
#coding=utf-8def bi_search(nums,target):
left = 0
right = len(nums) - 1res = []
while left <= right:
mid =(left + right) // 2 #left + (right - left) //2
#print(left,right)
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid -1
elifnums[mid] < target:
left = mid + 1return None推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- Docker应用:容器间通信与Mariadb数据库主从复制
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 第326天
- Shell-Bash变量与运算符
- 画解算法（1.|画解算法：1. 两数之和）
- 逻辑回归的理解与python示例
- Guava|Guava RateLimiter与限流算法
- 我和你之前距离
- CGI，FastCGI，PHP-CGI与PHP-FPM