数据结构与算法

排序查找算法

Posted by lily on April 7, 2023

线性表的查找

  • 按顺序依次往后查找
  • 时间复杂度：每次查找，循环减半,时间复杂度为O（logn） ```python class Solution(object): def search(self, nums, target): left = 0 right = len(nums) - 1 while left<=right: #还存在可查找空间 mid = (left + right)//2 #中间值索引为左边+右边整除2（中心偏左） if nums[mid] == target: return mid elif nums[mid] > target: #查询值在mid左边,左边界不动，移动右边界 right = mid - 1 else: left = mid + 1 else: return -1 #查询不到返回-1

### 二分查找闭区间模板

```java
    // 二分查找闭区间模板
    public int binSearch(int[] nums, int l, int r, int target){
        while (l<=r){
            int mid = l+(r-l)/2;
            if (nums[mid] < target){
                l = mid+1;
            }else{
                r = mid-1;
            }
            //  System.out.println("bin: "+l+", "+r+" "+mid);
        }
        // 判断是否越界且找到了target
        if (l < nums.length && nums[l]==target){
            return l;
        }
        return -1;
    }

    // 寻找排序数组的【第一个】最小值->最小值是数组断开的新起始点
    public int findMin(int[] nums){
        // 使用二分逻辑: 通过mid值与标准值的大小关系，判断需要左移r还是右移动l进而缩小查找区间，最后把查找值指向区间内唯一值
        // 标准值为nums[n-1]，这个值是数组旋转的切割点，需要找寻切割点才能分区间二分
        int n = nums.length;
        // 闭区间。特殊情况处理，1.不需要遍历到最后一位 2.当特殊情况时len=1，r=-1，不会进入循环
        int l=0, r=n-2;
        // 闭区间不为空
        while (l<=r){
            int mid = l+(r-l)/2;
            if (nums[mid] < nums[n-1]){
                // mid在后半区间，查找范围要向前移
                r = mid-1;
            }else {
                // mid在前半区间, 查找范围要向后移
                l = mid+1;
            }
            // System.out.println(l+", "+r+" "+mid);
        }
        return l;
    }
}

为什么要返回左边界

返回左边界下标 l 是正确的，原因如下：

  1. 二分查找的性质：在二分查找中，l 和 r 用来定义当前搜索的范围。l 是当前可能的最小索引，而 r 是当前可能的最大索引。当循环结束时，l 的位置是下一个应插入目标值的位置。

  2. 循环退出条件：当 l 大于 r 时，循环结束。在这种情况下，l 通常指向第一个大于目标值的位置，或者如果目标值存在，它将指向目标值的下标。

  3. 返回值的逻辑：
    • 如果目标值存在于数组中，l 会最终指向目标值的下标。
    • 如果目标值不存在，l 会指向插入位置，这样可以保证你可以在 l 的位置插入目标值而保持数组的排序。
  4. 右边界的使用：如果你返回右边界 r，在某些情况下（特别是当目标值在数组的末尾时），r 可能会指向一个不正确的位置，或者在目标值不存在的情况下可能会越界。 总结 因此，返回左边界 l 是合适的，它确保了无论目标值是否存在，代码都能正确处理并返回有效的索引。这样设计符合二分查找的逻辑，确保了高效性和准确性。

为什么需要判断左边界下标

依据题目需要：如果目标值不存在时会返回目标值该插入位置的下标，一般题目会要求目标值不存在时返回-1，所以需要判断返回左边界是否越界，如果未越界，那么插入位置是否为目标值，如果不是目标值那么说明没找到该值。

排序

  • 常见排序算法：
    • LowB排序算法：冒泡（bobble）排序，选择（select）排序，插入（insert）排序
    • NB排序算法：快速排序，堆排序，归并排序
    • 其他算法：希尔排序，计数排序，基数排序

      冒泡排序

  • 时间复杂度：O(n^2),两层循环 ，每次循环长度都为列表长度n。
  • image.png

    基本特点：

  • 时间复杂度：O(n^2)
  • 每排一轮，都会让有序区多一个数。
  • 原地排序：在原有列表上的基础上排序修改调整列表
    1. 外层循环控制这样冒泡的操作要来回几趟
    2. 内层循环控制每一趟相邻两个数之间的比较
    3. 外层循环长度：由于列表有n个数，需要把n-1个数冒泡上去（剩下最小的数自然就沉到了第0位），所以需要循环n-1趟。
    4. 内层循环长度：从第0位开始，用i0与i1进行比较；接着i1与i2进行比较；最后一位是i(n-1)与in进行比比较，所以内层循环指针应该最后指向第n-1，所以内层循环长度为n-1.
  • 代码： 
    def bobble_sort(list):
  for i in rang(len(list)-1):
      for j in rang(len(list)-1):
          #如果前一位的数大于后一位的数
          if list[j]>list[j+1]:
              #则交换位置
              list[j],list[j+1] = list[j+1],list[j]
          '''如前一位的数不大于后一位的数，这俩数不用交换位置，
          内层循环继续往前走，检查下两位相邻数字需不需要交换顺序'''
 #如果这一趟下来所有的数位次都不用交换，则说明列表已经排好了，
 #外层循环可以不用再继续了，所以可以用一个标志检验这一层循环是否
 #已经有序
def bobble_sort_verion2(li):
  for i in rang(len(li)-1):
      exchang = True
      for j in rang(len(li)-1):
          if li[j] > li[j+1]:
              li[j],li[j+1] = li[j+1],li[j]
              exchang = False
       if exchang:#说明内层循环一次也没交换过，可以退出循环了
          return

    选择排序

  • 时间复杂度：O(n^2)
  • 图解：

基本特点

  • 排序特点：把列表中最小的数找到，并放置（与第一个位置的数进行交换）到第一个位置上，直接挑出（select）最小的数与第一个位置数交换，不像冒泡排序，只与相邻的数比较且交换
    1. 遍历逻辑：在无序区中进行遍历，找到[无序区]最小数放入[有序区]的最后一位；有序区每新增一个数（每排好一遍），无序区遍历的起始位置就要向前挪一位。
    2. 核心步骤：
    1. 第一层遍历变量 i：
      1. 【i】表示有序区有多少个数，也表示下一个即将加入有序区数的索引
      2. 找到无序区开始处** i 最小数**下标x，记录该下标x
      3. 把x位置上的数放到 i 的位置上
    2. 第二层遍历变量 j ：
  • 代码实现 ```python def select_sort(li): for i in range(len(li)-1): #最后一个数不用排 # 找到当前最小的数 min_loc = i for j in range(i+1, len(li)): if li[j] < li[min_loc]: #直至找到最小的数 min_loc = j li[i], li[min_loc] = li[min_loc], li[i] ‘'’return li 不论是否return原来函数已经改变’’’

## 插入排序

- 时间复杂度：
- 图解：![image.png](https://cdn.nlark.com/yuque/0/2022/png/1238904/1659513264413-a47bfc32-5f9d-4f35-a6c9-3bf247be0699.png#averageHue=%23f4eeea&clientId=ue21e1b20-e4a1-4&errorMessage=unknown%20error&from=paste&height=115&id=u0a63be67&name=image.png&originHeight=172&originWidth=412&originalType=binary&ratio=1&rotation=0&showTitle=false&size=9874&status=error&style=none&taskId=ucfa971cf-cfa1-4d8f-b3b2-d04e6c5c10c&title=&width=274.6666666666667)
### 算法特点

1. 像打扑克牌一样把乱序的牌从头开始**选择插入的位置**，从而进行排序
2. 主要对‘’**有序区‘’** 进行操作，把后续未知大小的牌一张一张**插入**‘’**有序区**‘’
3. 一比较完就要交换位置，才能实现每一张符合条件的牌逐次向后移
4. 一个遍历**记录**程序现在运行（操作、排序）到何处，另一个遍历**操控**某张牌该如何 比较，并**最后**决定插入到哪个位置
5. 代码实现
```python
def insert_sort(li):
    for i in range(len(li)-1):
        pick_car = i+1  # 对下一张牌进行操作
        while pick_car >= 1 and li[pick_car] <= li[pick_car-1]:
            li[pick_car], li[pick_car - 1] = li[pick_car - 1], li[pick_car]
            pick_car -= 1

快速排序(quick_sort)

定义: 随即指针选择一个基准值, 在数组中交换基准值左右两边数的位置, 使得每次排序结束之后, 基准值左边的数(记左边数组A)都小于它, 右边的数(记右边数组B)都大于它的部分有序效果, 再递归两个A, B数组, 继续切分排序, 使得最后数组呈现从左到右非递减的有序的状态

快排模板一

注意: ==// 1. 当left=right 或者二者交叉时退出循环,此时left在pivot右侧,right在pivot左侧 // 2. 交叉部分可以理解为所有等于pivot指针的值

import java.util.Random;

public class Solution {
    /*
     * @param A: an integer array
     * @return: 
     */
    public Random rand;
    public void sortIntegers2(int[] A) {
        rand = new Random();
        // write your code here
        quickSort(A, 0, A.length - 1);
    }
    
    public void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }

        int index = rand.nextInt(end - start + 1)  + start;
        int pivot = A[index];
        int left = start;
        int right = end;
        
        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left ++;
            }
            while (left <= right && A[right] > pivot) {
                right --;
            }
            
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                
                left ++;
                right --;
            }
        }
        // 1. 当left==right 或者二者交叉时退出循环,此时left在pivot右侧,right在pivot左侧
        // 2. 交叉部分可以理解为所有等于pivot指针的值
        // A[start... right] 
        quickSort(A, start, right);
        // A[left ... end]
        quickSort(A, left, end);
    }
}

逻辑和步骤

一步步建立有序关系

  1. 排序部分: 用partition函数先归位第一个元素_tmp_（左右有序）
  2. 分治部分: 设计递归函数依次归位其余元素（每个元素都左右有序），完成排序。

归位partition函数的设计

  1. 右指针right移动，从右向左一直找到比_tmp_小的数放到left（此时tmp位置即为left位置）位置上，停止移动。
  2. 左指针left移动，从左向右比对直到找到比_tmp_大的数放到right的位置上，停止移动。

边界条件

  1. 小循环中设置**left<right ** ：
  2. data[right] >= tmp **小循环时遇上与tmp值相等的元素：当left与right未重合，但data[left] == data[right]**（left位与right位的数大小相同时），进不了小循环，left与right的值不能改变，又出不了大循环，此时会造成死循环。

三路快排

逻辑和步骤

快排模板二

代码实现：

def partition(data, left, right):
    tmp = data[left]
    while left < right:
        左边有空位，先从右边找元素补到左边
        '''直到找到符合条件的数再换位置，没找到就一直循环'''
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        '''找到大于tmp的数放到右边'''
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    '''最后right == left后tmp归位'''
    data[left] = tmp
    return left

_内层循环有无 left < right 的区别 _

data = [1,2,3,0]

def partition1(data, left, right):
    tmp = data[left]
    while left < right:
        while data[right] > tmp:
            right -= 1
        data[left] = data[right]
        while data[left] < tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return data

'''输出
[3, 0, 1, 2]'''

def partition2(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] > tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] < tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return data

'''输出
[0, 1, 3, 2]'''

def quick_sort(data,left,right):
   '''数据由传入函数参数获得
    left = 0
    right = len(data) - 1'''
    if left < right:  #递归终止条件
        #返回分割位置
        posi = partition(data, left, right)
        #调整posi左边
        quick_sort(data, left, posi-1)
        #调整posi右边
        quick_sort(data, posi+1, right)

逻辑和步骤

先交换Pivot指针指向的数到数组第一个位置, 最后再将pivot指针换回来, 使得pivot指针分割后数组左右两边分界明显, 再此基础上继续递归 图解：

  • 保存要固定元素
  • 逐步赋值并覆盖元素，以达到交换左右元素的目的
  • 把固定元素放回最后的空位

image.png

快排时间复杂度

一般情况

  • 一般情况下时间复杂度： O(nlogn)

image.png 涉及到递归，假设列表长度为16假设每一层都刚好把要排序的部分分割成两份，那么需要4层递归才能把所有的数排好顺序，24 = 16 ——>递归层数为 4 = log216 ——> 需要递归logn层 每层递归都要进行一次遍历列表长度n 所以粗略来算时间复杂度为 n*logn

最坏情况

  1. 递归深度限制
  2. 时间复杂度最坏情况

归并排序(merge_sort)

😥 递归-归并排序的基本步骤：

  1. 以中点进行数组划分，将待排序数组划分为left->mid, mid+1->right的两部分（探索左右边界）
  2. 一直划分至数组只有最小一个单位，不可再分，此时函数返回最后节点
  3. 合并时排序

    分治思想

    先将数组划分为最小只有一个单位，在合并的时候进行比较和排序

  4. 当要合并的左右两数组长度大于1时，需要分别移动左右两个数组的头指针进行比较，且需要另外一个指针指向新数组排序好的位置

    链表+递归+归并排序

    题目 ![[Pasted image 20240604000645.png]] 代码实现 ```java /**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode sortList(ListNode head) {

        // 递归终止条件

        if (head==null   head.next==null){

            return head;

        }

        // 拆分

        ListNode slow = head;

        ListNode fast = head.next;

        // 快慢指针查找中点, 快指针到达最后一个节点时，慢指针到达中点

        while (fast != null && fast.next!=null){

            slow = slow.next;

            fast = fast.next.next;

        }

        // 右半边链表头节点

        ListNode temp = slow.next;

        // 从中点切割数组

        slow.next = null;

        // 左边界为”头”节点，右边界为null，切割链表

        ListNode left = sortList(head);

        ListNode rigth = sortList(temp);

        // 构造假头节点

        ListNode doummyHead = new ListNode(0);

        // 保存当前两链表排序合并结束后的头节点(永远位于最左边)

        ListNode res = doummyHead;

        // 切割完毕后(递归结束后)合并

        // 合并左右链表

        while (left !=null && rigth !=null){

            // 稳定性，左边更小的还在前面

            if (left.val <= rigth.val){

                doummyHead.next = left;

                left = left.next;

            }else {

                doummyHead.next = rigth;

                rigth = rigth.next;

            }

            // 当前指针前移

            doummyHead = doummyHead.next;

        }

        // 合并剩下自然有序链表,左边排序剩余next指向左边，反之指向右边

        doummyHead.next = left!=null?left:rigth;

        return res.next;

    } }


## 堆排序（heap_sort）
### 树知识前传
![](https://cdn.nlark.com/yuque/0/2022/jpeg/1238904/1659756251892-c22eeebf-51f7-414c-9f53-61d49dd255be.jpeg)

**树：父亲节点与子节点的关系**

- **用数组来维护一棵完全二叉树**
- **知道父亲找孩子如果父亲节点在数组中索引为i，则左孩子为 ：left_child =ｉ＊ 2 +1；右孩子为：right_child = left_child + 1 = i * 2 + 2**
- **直到孩子找父亲 不管是左孩子还右孩子，父亲节点索引都为：i =（ child - 1） // 2 (在python中"//"为向下取整)。**
- **最后一个非叶子节点（父亲节点），列表长度为n， i = n//2 -1**
### 堆![image.png](https://cdn.nlark.com/yuque/0/2022/png/1238904/1659756046369-028333bf-2ec1-431e-867e-769505e883ca.png#averageHue=%23fcfcfc&clientId=ua178e4fb-c4d5-4&errorMessage=unknown%20error&from=paste&height=341&id=uf2bf0c94&name=image.png&originHeight=511&originWidth=624&originalType=binary&ratio=1&rotation=0&showTitle=false&size=59979&status=error&style=none&taskId=u9d688918-a2f0-4f9b-a35c-6f36762ba1e&title=&width=416)
根节点比子节点大的部分树结构或树结构为大根**堆**，构造大根堆或小根堆的过程叫做构造堆（heap）

---

### 基本逻辑

- 时间复杂度：
- ![image.png](https://cdn.nlark.com/yuque/0/2022/png/1238904/1659771691641-f1052ecf-3496-4cc8-a440-87a06623fbd9.png#averageHue=%23fdfdfd&clientId=ua178e4fb-c4d5-4&errorMessage=unknown%20error&from=paste&height=208&id=u21dbf9c0&name=image.png&originHeight=312&originWidth=436&originalType=binary&ratio=1&rotation=0&showTitle=false&size=45460&status=error&style=none&taskId=u63bc1d5a-902d-4bc7-a008-d6ce131c4d2&title=&width=290.6666666666667)
1. 构建堆
   1. 按照每一个父亲节点上的数都比子节点大进行构造，构造出来的堆在列表显示出**部分有序**
2. 从上往下进行堆调整
   1. 使得堆在列表显示出**全都有序**
- 代码实现：
```python
def sift(li, low, high):
    # 自上向下调整函数,调整为大根堆
    i = low
    j = i*2 + 1 # 左孩子
    tmp = li[i] # 保存要调整的数
    while j <= high:
        # !!如果右孩子存在且大于左孩子!!
        if j + 1 <= high and li[j] < li[j+1]:
            j = j + 1 # 让j指向更大的孩子
        if li[j] > tmp:
            # 若子节点比 tmp大，可把子节点往上提，继续向下一层检索
            li[i] = li[j]
            i = j
            j = i*2 + 1
        else:
            # 直到子节点到合适的位置退出循环
            break
    li[i] = tmp

def heap_sort(li):
    # 建造堆:从第一个非叶子节点开始从后向前局部调整
    deep = len(li)
''' 第一个非叶子节点可以从它的子节点反获取得到，
    它的孩子是列表里的最后一个数'''
    for leaf1 in range(deep//2-1, -1, -1):
        sift(li, leaf1, deep-1)
        
    # 排序堆：把最大数弹出后又调整生成最大数于根结点处
    for i in range(deep-1, -1, -1):
        # i 一直指向列表的最后一位，即指向最后一个叶子节点
    ''' 大根堆建造好后根节点数就是最大数，
     可以开始循环把最后一个数换到根节点上'''
    # 而最下面的位置则会依次被换成放置下来的最大数
        li[0], li[i] = li[i], li[0]
#  此时最低位i已经指向不用调整的最大数，所以最低位置为i-1
        sift(li, 0, 1-1)

topk问题——排序讨论

基本题目就是要找到数组中前K个最大的元素或者是找到第K个大的元素, 或者与之相关的变式

解决方法

  1. 构建小根堆——堆中只维护K个元素
    1. 堆顶元素会一直是K个数中最小的元素, 遍历整个数组, 如果有比堆顶大的元素则弹出堆顶, 将更大的元素放入堆中, 此时由于小根堆会自动维护, 将最小的元素又置于堆顶, 所以当遍历结束之后堆中的元素就是前K大个数
    2. 时间复杂度O(nlogk)，需要遍历一次整个列表，每次遍历到的那个数都有可能进入小根堆里进行调整，假若每个数都会调整一次，那么调整时间复杂度为O（logk），所以总的时间复杂度为O(nlogk)
  2. 冒泡排序——冒前k个数上去——不需要排所有的数
    1. 时间复杂度：O(nk)，每次冒泡都会把最大的数冒到顶端去，要冒k个数，单个数都要花费O（n）的时间，所以总计时间复杂度为O(nk)
  3. 快排——快速选择更偏向于高效查找，而不是保证局部的有序性
    1. 使用快排大于基准值的数放在左边,小于的放在右边
    2. 只递归大于基本只部分的数组,且当pivot==k-1停止递归直接返回该部分数组,时间复杂度降低为O(n)
    3. 当前pivot==k-1时, 前k个元素就是topk的元素
    4. 时间复杂度O(n)

小根堆

思路

实现: java中直接使用PriorityQueue, 自定义排序器或限定优先级队列大小为K

  • 如何用堆排序解决前k个大的数问题
    1. 从需要维护数据里获得前k个数，建立一个大小为k个数的小根堆。
    1. 此时堆顶为这k个数里面最小的数，即为第k大的数
      1. 遍历需要维护数据余下的数（列表里取出的前k个数之后的数），每次获取到的数与堆顶数进行比较，若大于堆顶数则进入小根堆进行调整，否则继续遍历下一个数。
    2. 调整即为维护小根堆的特性
      1. 遍历结束之后维护的小根堆里就是前k个数，逆序弹出就可以获得从大到小排列的前k大的数。
        • leetcode例题：前k个频率最高的数

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for(int num : nums){
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] m, int[] n){
                return m[1] - n[1];
            }
        });
        
        for(Map.Entry<Integer, Integer> entry : count.entrySet()){
            int num = entry.getKey(), cnt = entry.getValue();
            // 维护小根堆部分
            if(queue.size() == k){
                if(cnt > queue.peek()[1]){
                    queue.poll();
                    queue.offer(new int[]{num, cnt});
                }
            }else{
                queue.offer(new int[]{num, cnt});
            }
        }

        int[] res = new int[k];
        for(int i = 0; i < k; i++){
            res[i] = queue.poll()[0];
        }
        return res;
    }
}

快排

思路

i. 随机选一个中间值作为基准，并把它挪到最左侧 ii. 从第2个元素开始遍历，遍历过程中，要把比基准大的挪到左边，比基准小的挪到右边 iii. i 指向比基准大的元素，只要 j 指向的元素比基准小，就把 j 位置的元素和i后面一个位置的元素对调 并且i后移一位，这样 i 指向的元素以及i之前的元素都是比基准大的元素（基准本身除外） iv. j遍历到末尾后，此时i指向的就是排序后的列表中比基准大的最后一个元素，将该元素和基准对调，即 num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low] 这样排序后的列表就是在i位置前的都比 i 大，i 位置后的都比 i 小 接下来就是分治部分了 i. 如果 i == k - 1，也就是i及之前的元素恰好组成了我们想要的topK，直接返回前k个元素 ii. 如果 i > k - 1, 也就是i及之前的元素组成了top(K+N)，要对前 i 个元素再进行一次快排，从top(K+N)里选出topK findTopK(num_cnt, k, low, i - 1) iii. 如果 i < k - 1，也就是i及之前的元素组成了top(K-N)，要对i之后的元素再进行快排，在之后的元素中选出topN findTopK(num_cnt, k, i + 1, high) 返回快排结果中的数字部分

代码

public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int n:nums){

            map.put(n, map.getOrDefault(n, 0)+1);

        }

        List<int[]> newNums = new LinkedList<>();
		// 类型为Map的内部类Entry, map获取entry的方法
        for (Map.Entry<Integer, Integer> m:map.entrySet()){
            newNums.add(new int[]{m.getKey(), m.getValue()});
        }

        List<int[]> res = quickSort(newNums, k, 0, newNums.size()-1);

        int[] r = new int[k];

        for (int i=0;i<k;i++){

            r[i] = res.get(i)[0];

        }

        return r;

    }

    // 左闭右闭区间

    private List<int[]> quickSort(List<int[]> nums, int k, int l, int r){

        // 随机指针

        Random random = new Random();

        int p = l+random.nextInt(r-l+1);

        // 基准值

        int base = nums.get(p)[1];

        // 交换基准值与l下标值

        Collections.swap(nums, l, p);

        // i是有序的最左边界

        int i=l;

        for (int j=i+1;j<=r;j++){

            if (nums.get(j)[1] > base){

        // 比较交换部分,此时基准值已经位于数组左边界上，当找到一个大于基准值的数就将它放在排序好下标（当前下标为i）的后一位（i+1），而不是交换基准值与大于基准值的数

                Collections.swap(nums, i+1, j);

                // 并且此时排序好的指针范围扩大

                i++;

            }

        }

        // 排序结束之后将基准值与排序好的范围的最后一个数交换(因为中间可能有等于基准值的数)，归位逻辑完整

        Collections.swap(nums, l, i);

        // 分治部分

        if (i==k-1){

            // subList左闭右开

            // 返回排序好的前K个数最终结果

            return nums.subList(0, k);

        }else if (i>k-1){

            // i-1只递归乱序部分

            return quickSort(nums, k, l, i-1);

        }

        return quickSort(nums, k, i+1, r);

    }

统计元素个数（元素计数）

  • 假设列表里有大量重复且无序的数，如何高效统计每个元素出现的频率

    手写count函数

    内置count模块再转换为元组等连续数据存储

    哈希表存储

CATALOG
    FEATURED TAGS
    JAVASE JavaWEB Spring python基础 学习工具 数据结构与算法 爬虫学习 计算机网络 springBoot BugNotice springSecurity projectLearning SQL
    FRIENDS