一、快排

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