• 数据结构入门-14-排序

    在这里插入图片描述

    一、选择排序

    1.1 选择排序思想

    先把最小的元素拿出来
    剩下的，再把最小的拿出来
    剩下的，再把最小的拿出来
    在这里插入图片描述

    但是这样 空间复杂度是O(n)
    优化一下，希望原地排序

    1.1.2 选择原地排序

    在这里插入图片描述

    索引i指向0的位置
    索引j指向i+1的元素
    j 后面的元素遍历，找到最小的标记为minindex
    交换minindex 和 i
    在这里插入图片描述

    时间复杂度O(n^2)
    空间复杂度O(1)

    1.2 选择排序复杂度

    在这里插入图片描述
    第一轮 n 次，第二轮 n-1 次
    1 + 2 + 3 + … + (n-1) + n

    二、插入排序

    在这里插入图片描述

    扑克牌的排序 就是 插入排序

    2.1 插入排序思想

    在这里插入图片描述

    在这里插入图片描述

    j 往前 插入
    在这里插入图片描述

    时间复杂度O(n^2)
    空间复杂度O(1)

    三、冒泡排序

    基本思想：每次比较相邻的元素

    3.1 冒泡基本思想

    1. 第一轮两两比较大小

    在这里插入图片描述
    如果 > ,就互换
    在这里插入图片描述
    一直到最后
    在这里插入图片描述
    第一轮之后，最大的元素一定在最后
    所以在第二轮，最后一个元素就不用比较了

    1. 第二轮
      在这里插入图片描述
    2. 第三轮
      在这里插入图片描述
    3. 第n - 1轮
      在这里插入图片描述

    3.2 冒泡过程理解

    在这里插入图片描述

    平均时间复杂度：O(n^2)
    空间复杂度O(1)

    四、归并排序MergeSort

    更加复杂的递归算法

    O(nlogn)的时间复杂度

    4.1 归并思想

    在这里插入图片描述
    将一个数组一分为二 ，分别排序，得到两个排序后的子数组

    在这里插入图片描述

    对两个子数组排序的方法还是继续划分

    MergeSort(arr, l, r)
对 arr数组的 l 到 r 区间进行排序

    • 1
    • 2

    4.2 归并步骤

    1. 递归排序的算法：
    MergeSort(arr, l, r) 

    • 1
    1. 找到切分的中点
    int mid = (l + r) / 2

    • 1
    1. 对arr[l , mid] 进行排序
    MergeSort(arr, l, mid) 

    • 1
    1. 对arr[mid + 1, r] 进行排序
    MergeSort(arr, mid+1, r) 

    • 1
    1. 将arr[l,mid] 和 arr[mid+1,r]进行合并
    merge(arr, l, mid, r) 

    • 1
    1. 设置递归调用的终止条件
    if(l >= r) return;

    • 1

    在这里插入图片描述

    4.3 归并merge过程思想

    在这里插入图片描述

    1. A[1] 和 B[1] 对比，谁更小，谁进入Result
      在这里插入图片描述
    2. 持续对比头上的点
      在这里插入图片描述

    4.4 merge 过程详解

    1. 计算mid
      在这里插入图片描述

    2. 将数据复制一份，标记左右 i ， j = mid + 1
      在这里插入图片描述

    3. 使用i j 两个索引 对比，result 直接写入原区间
      在这里插入图片描述

    4. 终止条件：i >= mid , j > r
      在这里插入图片描述
      在这里插入图片描述
      归并排序过程无法原地完成

    4.5 归并复杂度分析

    空间复杂度：由于需要 copy 一份出来，所以是O(n)

    时间复杂度：

    在这里插入图片描述
    MergeSort：每一层总和都会有 n
    一共有 logn层

    所以是O(n logn)

    在这里插入图片描述

    五、希尔排序

    冒泡排序每次只能一位
    希尔排序希望 很大的元素能够很快的移动到最后面

    5.1 希尔排序思想

    1. 距离为4 （n/2）分组
      在这里插入图片描述

    2. 每一组内，元素进行插入排序
      在这里插入图片描述
      完成一轮组内的插入排序之后
      在这里插入图片描述

    3. 距离为2 （n/4）分组
      在这里插入图片描述

    4. 再次组内插入排序
      在这里插入图片描述

    5. 距离为（n/8）的排序
      由于只有8个，所以也就是array本身
      全体进行插入排序

    在这里插入图片描述

    5.2 为什么中间要用插入排序

    希尔排序经过前面的分组内排序之后，
    数组已经大体上都是有序的了
    插入排序只需要找到前面一个不小于的即可
    因此 最后 插入排序会省一些前面的比较步骤

    在这里插入图片描述

    5.3 希尔排序的复杂度

    在这里插入图片描述
    在这里插入图片描述

    因此也称为 O(n^1.5)

    六、快速排序QuickSort

    20世纪对世界影响最大的算法之一

    6.1 快排原理

    归并排序不管数组的内容，直接一分为二，再进行排序
    快排从当前数组中选择一个元素当作基点
    在这里插入图片描述
    比如选择了4当作基点，前面都 < 4,后面都 > 4

    如何将4移动到正确的位置，就是快排的核心

    在这里插入图片描述
    这个将基点移动到正确位置的过程，称为partition

    在这里插入图片描述

    如何获取 基准 元素？
    随便获取就可以，最简单的就是直接获取第一个元素

    在这里插入图片描述
    partition的返回值是 p （标定点对应的索引）

    递归函数的宏观语意：
quickSort(arr, l, r)
对arr中 l 到 r 的排序

    • 1
    • 2
    • 3

    在这里插入图片描述

    6.2 partition过程详解

    6.2.1 非原地partition

    在这里插入图片描述

    开辟两个临时数组left right
    不是原地排序

    6.2.2 原地partition

    在这里插入图片描述

    L:基准元素
J:<>分界点
i:当前访问的元素

    • 1
    • 2
    • 3

    当e >= v的时候

    i ++ 就好了
    e直接并入大的区间

    当e < v的时候
    在这里插入图片描述

    只需要将j+1个元素和e进行互换
    j++即可

    在这里插入图片描述
    最后将L的位置和J的位置进行互换

    6.2.3 举例partition

    1. 初始化，i j l
      在这里插入图片描述

    2. 比基准大
      在这里插入图片描述

    3. 比基准小
      在这里插入图片描述
      J++ ，扩充前面的元素
      交换i j 指向的元素

    在这里插入图片描述
    4) 交换l j基准点
    在这里插入图片描述

    retrun j

    后续再对前面 和 后面 进行递归的QuickSort

    6.3 快排复杂度分析

    归并排序
    快排的复杂度 和 之前归并的复杂度分析是相思的

    在这里插入图片描述
    在这里插入图片描述
    快速排序

    快排可能是不平均的两部分
    在这里插入图片描述
    在这里插入图片描述
    虽然快排的最差情况是O(n^2)的，但是概率很低，
    大概率还是O(nlogn)
    在这里插入图片描述

    partition原地排序：空间复杂度O(1)
    partition非原地排序：空间复杂度O(logn)

    七、堆排序

    7.1 优先队列

    出队顺序和入队顺序无关，和优先级相关
    例如OS中任务进程的调度

    在这里插入图片描述
    上浮下沉 Sift UP Sift Down
    在这里插入图片描述

    下沉操作，复杂度为O(logn),可以重新构建成堆

    在这里插入图片描述
    时间复杂度：O(nlogn), 空间复杂度：O(1)

  • 相关阅读:
    [黑马程序员C++笔记]P174-P184模板-类模板
    这些4K手机、电脑壁纸网站，你一定要知道
    input 表单元素
    css-vxe-form-item中输入框加自定义按钮（校验位置错误）
    手动模拟 calico 网络
    【Java】集合（一）单列集合List
    超级水王问题
    Wireshark 通过 nrf-sniffer for BLE 抓包环境配置说明
    分享一下我家网络机柜，家庭网络设备推荐
    北邮22级信通院数电：Verilog-FPGA（2）modelsim北邮信通专属下载、破解教程
  • 原文地址：https://blog.csdn.net/weixin_39381833/article/details/132869305