一、快排
image
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）
算法流程：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码：
1. 递归方法
2. 非递归方法（栈）
3. 非递归方法（不用栈）【待补充】
class sortfunc():
def partition(self,nums,left,right):
small = left
p = small+1
while p<=right:
if nums[p]<nums[left]:
small += 1
nums[small],nums[p]=nums[p],nums[small]
p+=1
nums[left],nums[small]=nums[small],nums[left]
return small
# 递归
def quicksort1(self,nums,left,right):
if left<right:
s = self.partition(nums,left,right)
self.quicksort1(nums,left,s-1)
self.quicksort1(nums,s+1,right)
return nums
# 非递归+栈
def quicksort2(self,nums):
stack = []
left = 0
right = len(nums)-1
if left<right:
s = self.partition(nums,left,right)
if left < s-1:
stack.append(left)
stack.append(s-1)
if right > s+1:
stack.append(s+1)
stack.append(right)
while stack:
right = stack.pop()
left = stack.pop()
s = self.partition(nums,left,right)
if left < s - 1:
stack.append(left)
stack.append(s - 1)
if right > s + 1:
stack.append(s + 1)
stack.append(right)
return nums
4. partition函数可以用来解topk问题，前提是数据有限可以一次性存到数组nums里
topk方法：
1. 快排+截前k个
时间复杂度：O(nlogn)+O(k)=O(nlogn)。
得到的是已经排好序的前k个值
2. 小根堆【待更新】
时间复杂度O(k+(n-k)logk)=O(nlogk)
堆是一种特殊的数据结构，它的通常的表示是它的根结点的值最大或者是最小。
python中heapq的使用
堆顶（heap[0]）为最小值
每个元素与堆顶比较，大于堆顶则替换堆顶，堆中始终为最大的k个数
这样最终得到的是最大的k个数，要想得到最小k个，只要把输入arr改为-arr就可以了
这里代码找的是最大的k个数，同样没有顺序：
def topk_heap(self,nums,k):
result = []
for i in nums:
if len(result)<k:
heapq.heappush(result,i)
else:
res_min = result[0]
if i>res_min:
heapq.heapreplace(result,i)
return result
3. 快排分治法
时间复杂度O(n)
得到的是没有排序（可能排了一部分）的数组
如果要按顺序排列的话，最后还要对这k个数排序（topk问题本身不要求排序，只要找到第k小（大）的元素）
排序后时间复杂度：O(n)+O(k*logk)
# 求前k个小的数
def topksmall(self,nums,k):
if not nums:
return []
if k<=0:
return []
if k>len(nums):
return []
s = self.partition(nums,0,len(nums)-1)
while not s==k-1:
if s<k-1:
s = self.partition(nums,s+1,len(nums)-1)
if s>k-1:
s = self.partition(nums,0,s-1)
return sorted(nums[:k]) #这里排序了，为了后面方便使用。。。
5. leetcode里的topk问题：
- 692、给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
def topKFrequent(self, nums, k):
dic = {}
for i in nums:
if not i in dic:
dic[i] = 1
else:
dic[i] += 1
dic1 = list(dic.items())
num = [x[0] for x in dic1]
count = [x[1] for x in dic1]
m = max(count)
# print(num)
# print(count)
for j in range(len(count)):
count[j] = m-count[j]
# print('count=',count)
'''注意这里要deepcopy一哈，把值复制过来，不然会改变count的值！！！'''
count2 = copy.deepcopy(count)
count1 = self.topksmall(count2,k)
# print(count)
# count2 = copy.deepcopy(count1)
s = []
for l in count1:
tmp = count.index(l)
s.append(num[tmp])
count[tmp]=-1
return s
P.S. 实际问题
实际上，具体采用哪种方法，要根据实际场景决定
分治法时间复杂度低，空间复杂度高
最小堆方法时间复杂度高，空间复杂度低
（1）足够大内存——分治法
（2）多核——多线程处理，划分数据后再归并
（3）单核+受限内存——划分数据后依次处理
*自己写给自己看的博客
*文章内容不保证正确
*部分内容来源于网络，侵删
今天也是元气满满的一天哦~~
冲鸭~~QWQ
