知行合一
Github
顺翔的技术驿站
顺翔的技术驿站
  • README
  • ABOUTME
  • Computer Science
    • 数据结构与算法
      • 位运算以及位图
      • 随机数
      • 递归
      • 经典排序算法
      • 经典查找算法
      • 数组和动态数组
      • 链表
      • 栈和队列
      • 树
      • 哈希表
    • 计算机网络
      • 物理层
      • 数据链路层
      • 网络层
        • TCP
      • 运输层
      • 应用层
      • HTTP
        • HTTPS的原理
        • DNS详解
        • file协议
        • 邮件协议
    • 设计模式
      • 单例模式
      • 建造者模式
      • 原型模式
      • 工厂模式
      • 享元模式
      • 代理模式
      • 装饰者模式
      • 桥接模式
      • 适配器模式
      • 外观模式
      • 组合模式
      • 事件驱动
      • 有限状态机
      • 备忘录模式
      • 模板方法模式
      • 策略模式
      • 迭代器模式
      • 命令模式
      • 解释器模式
    • 加密与解密
      • 数字证书原理
      • cfssl
  • Programming Language
    • 编程语言学习要素
    • Java
      • 集合
        • List
          • ArrayList
          • Vector
          • Stack
          • LinkedList
        • Iterator
        • Set
          • HashSet
          • TreeSet
        • Map
          • HashMap
          • HashTable
          • TreeMap
          • LinkedHashMap
      • 常用API
        • 日期时间处理
        • System
        • Random
        • Arrays
        • Scanner
        • 格式化输出
      • java特性
        • java5特性
        • java8特性
        • java9特性
        • java10特性
        • java11特性
      • 并发编程
        • 线程基础
        • 线程同步:synchronized及其原理
        • 线程同步: volatile
        • 锁机制
        • 锁的分类与对应的Java实现
        • JUC:同步辅助类
        • JUC: AtomicXXX
        • 线程池
        • ThreadLocal详解
      • 测试
        • 使用JMH进行基准测试
      • JVM
        • 强引用、软引用、弱引用、虚引用
        • jvm内存模型
        • jvm优化
        • GC算法与回收器
        • 静态绑定与动态绑定
      • ORM
        • Mybatis
          • IBatis常用操作
      • Web编程
        • Servlet详解(一)
        • Servlet详解(二):request和response对象
        • Servlet详解(三):会话技术与Cookie
        • JSP详解(一):页面构成、EL表达式
        • JSP详解(二):九大内置对象
        • JavaWeb的编码问题
        • Thymeleaf
      • Velocity
      • Java日志框架总结
      • Spring
        • SpringIOC
        • SpringMVC
        • SpringBoot源码
      • 其他
        • Apache Commons Lang使用总结
        • 使用FtpClient进行ftp操作
        • Java PDF操作总结
        • Java使用zip4j进行文件压缩
        • Java解析Excel总结
    • JVM Language
      • Groovy
      • Scala
    • Kotlin
      • 变量和常量
      • 数据类型
        • 基本数据类型
        • 容器类型
        • 函数类型
        • null和null安全
      • 流程控制
      • 包
      • 面向对象
    • Golang
      • 关键字与标识符
      • 变量和常量
      • 数据类型
      • 函数
      • 常用API
        • 时间日期处理
        • 字符串操作
        • 正则表达式
      • 控制语句
      • 包package
      • 面向对象
      • 错误处理
      • 命令行编程
        • Cobra
      • 文件操作
      • 测试
      • 并发编程
        • sync包详解
      • 数据格式与编码
        • 使用encoding包操作xml
        • 使用encoding包操作json
        • 使用magiconair操作properties
        • 使用go-ini操作ini
      • 反射
      • Build Tools
        • Go Module
        • Go Vendor
      • 日志框架
        • zap日志框架
      • Web编程
        • Gin
    • JavaScript
      • 数据类型
      • ECMAScript
        • ECMAScript6
      • NodeJS
    • TypeScript
      • 变量和常量
      • 数据类型
      • 函数
      • 面向对象
      • 泛型
      • Build Tools
        • tsc编译
        • 与webpack整合
    • Python
      • BuildTools
        • requirements.txt
        • Ananconda
    • Swift
      • 变量和常量
    • Script Language
      • Regex
      • BAT
      • Shell
    • Markup Language
      • Markdown
      • Yaml
  • Build Tools
    • CMake
    • Maven
      • 搭建Nexus私服
      • maven使用场景
    • Gradle
  • Version Control
    • Git
      • Git工作流
      • Git分支管理
      • Git Stash
      • Git Commit Message规范
      • .gitttributes文件
    • SVN
  • Distributed
    • 分布式基础理论
      • 互联网架构演变
      • 架构设计思想AKF拆分原则
      • CAP理论
      • BASE理论
    • 一致性
      • 一致性模型
      • 共识算法
        • Paxos
        • Raft
        • ZAB
      • 复制
        • 主从复制
        • Quorum机制
        • Nacos Distro协议
      • 缓存一致性
        • 双写一致性
        • 多级缓存一致性
    • 事务一致性
      • Seata
      • 本地消息表实现方案
      • 关于dpad的事务问题的分析
    • IO
    • RPC协议
    • 序列化
    • Session共享
    • 分布式协调
      • Zookeeper
        • zk集群4节点搭建
    • 服务治理
      • Dubbo分布式治理
    • 分布式ID
      • 分布式ID生成策略总结
    • 分布式锁
    • 应用服务器
      • Tomcat
    • Web服务器
      • Nginx
        • Nginx的基本配置
        • ab接口压力测试工具
        • nginx模块
        • 随机访问页面
        • 替换响应内容
        • 请求限制
        • 访问控制
        • 状态监测
        • nginx应用场景
        • 代理服务
        • 负载均衡
        • 缓存
        • 静态资源服务器和动静分离
        • 附录
      • Kong
    • 缓存中间件
      • Caffeine
      • memcached
      • Redis
        • Centos下安装Redis
        • RatHat下安装Redis
    • 数据库中间件
      • ShardingSphere
      • MyCat2
    • 消息中间件
      • Kafka
      • RocketMQ
  • Microservices
    • 服务发现
      • Nacos注册中心
      • Consul
    • 配置中心
      • Apollo
    • 消息总线
    • 客户端负载均衡
    • 熔断器
    • 服务网关
    • 链路追踪
      • Skywalking
  • Domain-Specific
    • Auth
      • 有关权限设计的思考
      • 认证方式
      • JWT
    • 任务调度
      • QuartzScheduler
      • Elastic-Job
      • XXL-Job
      • PowerJob
    • 工作流
      • BPM
      • Activiti
      • Flowable
    • 规则引擎
      • Drools
  • Architect
    • DDD领域驱动设计
      • 三层架构设计
      • 四层架构设计
    • Cola
    • 代码设计与代码重构
      • 重构改变既有代码设计
      • 枚举规范化
      • 接口幂等
      • 限流
      • 历史与版本
      • 逻辑删除和唯一索引
      • 业务对象设计
    • 单元测试
      • SpringBoot单元测试实践
    • 项目管理
    • APM
      • SkyWalking
      • Arthas
    • 性能优化
      • 接口性能优化
    • 系统设计
      • 流程中台
      • 短信中台
      • 权限中台
        • 智电运维平台组织架构改造二期
  • Database
    • Oracle
      • Docker下安装oracle11g
    • IBM DB2
    • Mysql
      • 安装Mysql
      • 用户与权限管理
      • MySQL的逻辑架构
      • 存储引擎
      • 索引详解
      • MySql的列类型
      • MySql中表和列的设计
      • MySql的SQL详解
      • 锁机制
      • 事务
      • Mysql函数总结
      • MySql存储过程详解
      • MySql触发器详解
      • Mysql视图详解
      • Mysql中Sql语句的执行顺序
      • 配置MySql主从和读写分离
      • MySql的备份策略
      • MySql分库分表解决方案
      • MySql优化总结
      • MySQL实战调优
        • schema与数据类型优化
    • Mongo
  • File System
    • README
    • HDFS
    • FastDFS
    • MinIO
  • Linux
    • 常用的Linux命令
    • vim
    • Linux磁盘管理
    • Linux系统编程
    • RedHat
      • rpm包管理器具体用法
    • Ubuntu
      • Ubuntu下录制屏幕并做成gif图片
      • Ubuntu20.05LiveServe版安装
  • DevOps
    • VM
      • 新建一个新的Linux虚拟机需要配置的东西
      • VMware桥接模式配置centos
      • VMwareFusion配置Nat静态IP
    • Ansible
    • Container
      • Docker
        • Dockerfile详解
        • DockerCompose详解
      • Containerd
    • Kubernetes
      • 安装k8s
        • 使用Minikube安装k8s
        • centos7.x下使用kubeadm安装k8s1.21
        • ubuntu20下使用kubeadm安装k8s1.21
        • centos7.x下使用二进制方式安装k8s1.20
        • 使用DockerDesktop安装K8s(适用M1芯片)
      • 切换容器引擎
      • 使用k8s部署项目的流程
      • 集群维护-备份升级排错
    • Gitlab
      • GitlabCI/CD
    • CI/CD
      • ArgoCD
  • Big-Data
    • Hadoop
    • MapReduce
    • HDFS
  • Front-End
    • Android
      • Log的使用、自定义Log工具类
      • Android倒计时功能实现
      • 解决ViewDrawableLeft左侧图片大小不可控的问题
      • AndroidSQLite基本用法
      • View的生命周期
      • 工具类
      • WebView详解
      • ViewTreeObserver类监听ViewTree
      • 在onCreate中获取控件的宽高等信息的几种方法
      • View的foreground属性
        • MaterialDesign
          • BottomNavigationBar
          • CardView
          • Elevation高度、shadows阴影、clipping裁剪、tint着色
          • TouchFeedbackRipple波纹动画
      • Volley完全解析——使用、源码
      • Android围住神经猫的实现
      • LookLook剖析,架构概述——MVP、Retrofit+RxJava
      • Android性能优化之渲染
    • Browser
      • 浏览器的工作原理
    • HTML
      • DOCTYPE标签、XHTML与HTML的区别
    • CSS
      • CSS的继承性、层叠性、权重
      • CSS浮动float详解(一):标准文档流
      • CSS浮动float详解(二):使用float
      • CSS浮动float详解(三):清除浮动方案
    • Tools Lib
      • JavaScript 文件下载解决方案-download.js
      • js-url 用于url的js开源库
      • jsuri 用于操作url的js开源库
      • window offset
    • React
      • 模块化和组件
      • 组件的三大核心属性
      • 事件处理
      • 表单数据收集
      • 生命周期
      • DOM的diff算法
      • 工程化
        • 脚手架create-react-app
        • 工程结构和模块化
      • 路由
  • Design
    • 产品设计
      • 交互设计
由 GitBook 提供支持
在本页
  • 选择排序
  • 冒泡排序
  • 插入排序
  • 归并排序
  • 递归实现
  • 非递归实现
  • 小和问题
  • 快速排序

这有帮助吗?

在GitHub上编辑
  1. Computer Science
  2. 数据结构与算法

经典排序算法

上一页递归下一页经典查找算法

最后更新于1年前

这有帮助吗?

选择排序

public static void selectionSort(int[] arr) {
  if (arr == null || arr.length < 2) {
    return;
  }

  // 找出 0 ~ n-1 中的最小值的索引
  // 找出 1 ~ n-1 中的最小值的索引
  // 找出 2 ~ n-1 中的最小值的索引
  // 找出 i ~ n-1 中的最小值的索引
  for (int i = 0; i < arr.length; i++) {
    int minValueIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
      minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
    }
    // 交换值,将每次最小都放入前面
    swap(arr, i, minValueIndex);
  }
}

private static void swap(int[] arr, int i, int j) {
  int iV = arr[i];
  arr[i] = arr[j];
  arr[j] = iV;
}

@Test
public void testSelectionSort() {
  int[] arr = new int[]{1, 3, 5, 3, 2, 9, 2, 5};
  selectionSort(arr);
  System.out.println(Arrays.toString(arr));
}

时间复杂度:

两层循环 O(N^2)

冒泡排序

依次比较相邻的数,并交换,最后将最大的数冒泡到最后,这样循环 n-1 次后,即可排序所有数。

public static void bubbleSort(int[] arr) {
  if (arr == null || arr.length < 2) {
    return;
  }
  // 0 ~ n-1
  // 0 ~ n-2
  // 0 ~ n-3
  // 0 ~ n-4

  // 也就是 0 ~ end
  for (int end = arr.length - 1; end >= 0; end--) {
    // 在 0 ~ end 上对数进行两两比较,将最大的数冒泡到最后
    // 需要循环 end-1 次,倒数第二次循环已经将最大值选出了
    for (int i = 0; i <= end - 1; i++) { // 从1开始是为了不溢出
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1);
      }
    }
  }
}

@Test
public void testBubbleSort() {
  int[] arr = new int[]{1, 3, 5, 3, 2, 9, 2, 5};
  bubbleSort(arr);
  System.out.println(Arrays.toString(arr));
}

时间复杂度:

  1. 假设数组长度为 n,交换方式是最坏的情况,每次都要交换

  2. 那么交换次数为: n, n-1, n-2, ... 3, 2, 1

  3. 根据等差数列公式,Sn=n*a1+n(n-1)d/2 或者 Sn=n(a1+an)/2,可以得到数据量级n与交换次数之间的关系为 (1/2)*(n^2) -(1/2 -a1)n

  4. 保留最高次项,故冒泡排序的时间复杂度为O(n^2)

插入排序

插入排序之所以叫插入排序,是因为他的排序过程类似扑克游戏斗地主的摸牌的排序过程。

public static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    // 0 ~ 0 
    // 0 ~ 1 范围有序
    // 0 ~ 2 范围有序
    // ...   
    // 0 ~ n 范围有序
    for (int end = 0; end < arr.length; end++) {
        // 排序新数
        int newNumIndex = end;
        while (newNumIndex - 1 >= 0 && arr[newNumIndex-1] > arr[newNumIndex]) {
            swap(arr, newNumIndex -1, newNumIndex);
            newNumIndex--;
        }
    }
}

时间复杂度:

O(N^2)

归并排序

归并排序是时间复杂度为O(n*logn)。

递归实现

  1. 让数组arr的L到R位置上有序

  2. 将数组拆分为两半,确认中间位置 (L+R)/2 = M

  3. 让 L到M, M+1到R范围内有序

  4. 左右部分排序成功后,准备一个R-L长度的数组空间,同时遍历左右空间,每次取出一个元素,比较两个两个数字的大小。谁小将谁放额外数组空间中,这样就完成了结果的归并

  5. 就这样这样依次对半拆分排序,直到不能再拆分,再依次归并,即可完成归并排序

/**
 * 递归实现归并排序
 */
public void mergeSort1(int[] arr, int L, int R) {
  if (arr == null || arr.length < 2
      || L < 0 || L >= arr.length
      || R < 0 || R >= arr.length || L >= R) {
    return;
  }
  process(arr, L, R);
}

public void process(int[] arr, int L, int R) {
  if (L == R) {
    return;
  }
  int M = (L + R) / 2;
  process(arr, L, M);
  process(arr, M + 1, R);
  merge(arr, L, M, R);
}

public void merge(int[] arr, int L, int M, int R) {
  int[] help = new int[R - L + 1]; // 创建一个用于盛放合并后数组的数组
  int i = 0; // help的指针,每次填充后+1
  int p1 = L; // 遍历左部分的指针
  int p2 = M + 1;// 遍历有部分的指针

  // p1 p2 都在正确的范围内
  while (p1 <= M && p2 <= R) {
    help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
  }

  // 如果p1在正确的范围内,说明p2循环完毕了
  while (p1 <= M) {
    help[i++] = arr[p1++];
  }

  //  如果p2在正确的范围内,说明p1循环完毕了
  while (p2 <= R) {
    help[i++] = arr[p2++];
  }

  // 将help排序后的内容填充到arr中
  for (i = 0; i < help.length; i++) {
    arr[L + i] = help[i];
  }
}

@Test
public void testMergeSort1() {
  int[] arr = new int[]{7, 9, 3, 1, 0, 1, 4, 5, 9, 8, 0, 2};
  mergeSort1(arr, 0, 5);
  System.out.println(Arrays.toString(arr));
}

复杂度:

T(n) = aT(n/b) + O(N^d)
T(n) = 2T(n/2) + O(N^1)
a = 2, b = 2, d = 1
logbA = 1 == d,那么时间复杂度为  O(N^d * logN) ,即 O(N*logN)

也可以使用for循环替代while:

package com.rhdk.contractservice;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {

        // 递归实现归并排序
        int[] arr = new int[]{2, 1, 3, 4};
        mergeSort1(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int M = (L + R) / 2;
        sort(arr, L, M);
        sort(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int lIndex = L;
        int rIndex = M + 1;

        for (int i = 0; i < help.length; i++) {
            if (lIndex > M && rIndex > R) {
                break;
            }

            if (lIndex > M) {
                help[i] = arr[rIndex++];
                continue;
            }

            if (rIndex > R) {
                help[i] = arr[lIndex++];
                continue;
            }

            if (arr[lIndex] <= arr[rIndex]) {
                help[i] = arr[lIndex++];
            } else {
                help[i] = arr[rIndex++];
            }
        }

        // 填充到原数组
        if (R + 1 - L >= 0) {
            System.arraycopy(help, 0, arr, L, R - L + 1);
        }
    }

}

非递归实现

  1. 递归是将数组拆分为两半,而这种方式则是将元素分为固定的k组,整体思想是相同的

  2. k=1:循环数组,因为数组在[0,0]、[1,1]、[2,2]、[3,3]...范围内有序,合并有序数组,让数组在[0,1]、[2,3]、[4,5]...范围内有序

  3. k=2:循环数组,因为数组在[0,1]、[2,3]、[4,5]、[6,7]...范围内有序,合并有序数组,让数组在[0,3]、[4,7]、[8,11]...范围内有序

  4. k=4:循环数组,因为数组在[0,3]、[4,7]、[8,11]...范围内有序,合并有序数组,让数组在[0,7]、[8,15]、[16,23]...范围内有序

  5. k=?:循环数组,因为数组在[i, i+k-1]范围上有序,合并有序数组,让数组在 [i + 2k-1]范围内有序

  6. 如此循环数组,直到k>=arr.length时,即完成了数组的排序

  7. 注意边界不能超过数组的长度

  8. 如此循环,将2个有序的小组,合并为4个有序的小组

  9. 此时让 k=4,按照上述流程继续循环,将4个7有序的小组合并为8个有序的小组

  10. 如此反复,

代码如下:

public void mergeSort2(int[] arr) {
  int k = 1;
  int i = 0;
  while (k <= arr.length) {
    if (i >= arr.length) {
      i = 0;
      k <<= 1;
    }
    // 左索引为i,右索引为 i + 2 * k - 1,且不能超过数组长度-1,中间为i + k - 1,且不能超过数组长度
    int L = i;
    int R = Math.min(i + 2 * k - 1, arr.length - 1);
    int M = Math.min(i + k - 1, arr.length - 1);
    // 将小组合并为大组
    merge(arr, L, M, R);
    // 重置i索引
    i += 2 * k;
  }
}

@Test
public void testMergeSort2() {
  int[] arr = new int[]{9, 7, 3, 1, 0, 1, 4, 5, 9, 8, 0, 2};
  mergeSort2(arr);
  System.out.println(Arrays.toString(arr));
}

时间复杂度:

while (k <= arr.length) 
i += 2 * k;
每次使用x2的方式追赶问题规模N,故外层复杂度为 logN

每当if (i >= arr.length) 重新开始循环,这是内层循环
内层循环只走了merge方法,时间复杂度为N

所以时间复杂度也为 O(N * logN)

为什么选择、冒泡、插入排序O(n^2)的时间复杂度劣于归并排序O(N * logN)?

因为前者在比较时,将所有的数依次比较,很多比较行为并没有交换,造成了很多无效的操作。

小和问题

假设有个数组, [6, 3, 4, 6, 7],

  1. 第0个元素左侧比该元素小的值的总和为0

  2. 第1个元素左侧比该元素小的值的总和为0

  3. 第2个元素左侧比该元素小的值的总和为3

  4. 第3个元素左侧比该元素小的值的总和为3+4=7

  5. 第4个元素左侧比该元素小的值的总和为6+3+4+6=19

  6. 故最小和为 3 + 7 + 19 = 29

要求复杂度为 O(N*logN)

快速排序

快排的步骤:

  1. 以数组中最后一个数字P为边界,将数组内的小于等于P的数放在左侧,大于P的数放右侧

  2. 当前数 <= P,当前数在 <= 区,当前数与下一个数交换,<= 区扩容1,当前数指针向后移动一次

  3. 当前数 > P,当前数指针向后移动

849589-20171015224719590-1433219824
9916080-f0605d250bd43468
849589-20171015225645277-1151100000
img