当前位置: 首页 > news >正文

排序算法(一)

1.冒泡排序-Bubble Sort

1.算法原理

        依次比较相邻的两个元素,若按照从小到大的顺序,则将相邻元素中较大的一个放在后面;然后对每一对相邻元素都做这种比较,序列的最后一个元素就是最大的数;

2.算法复杂度

时间复杂度:最优复杂度:O(n);最差复杂度:O(n2);平均复杂度:O(n2)

空间复杂度:O(1)

3.算法实现-Java

public int[] bubbleSort(int[] arr){for(int i = 0; i < arr.length - 1; i++){for(int j = 0; j < arr.length -1 - i; j ++){if(arr[j] > arr[j + 1]){int temp = arr[j];int arr[j] = arr[j + 1];int arr[j + 1] = temp;}}}return arr;
}

 

2.选择排序-Selection Sort

1.算法原理

        先在需要排序的序列中找到最大(小)的一个元素,将其放到序列的起始位置

        然后在剩余队列中找到最大(小)的一个元素,将其放到已经排列好的序列的末尾

        以此类推

2.算法复杂度

时间复杂度:最优复杂度:O(n2);最差复杂度:O(n2);平均复杂度:O(n2)

空间复杂度:O(1)

3.算法实现-Java

public int[] selectionSort(int[] arr){for(int i = 0; i < arr.length-1; i++){int minIndex = i;for(int j = i + 1; j < arr.length; j ++){if(arr[j] < arr[minIndex]){minIndex = j;}}if(minIndex != i){int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}return arr;
}

3.插入排序-Insertion Sort

1.算法原理

        假设第一个元素为已排好序的序列,未排序的元素从已排好序的序列中从后向前扫描,找到相应的位置插入进去(原本这个位置的元素向后挪一位),组成新的已排好序的序列;以此类推,直到所有元素排序完成    

2.算法复杂度

时间复杂度:最优复杂度:O(n);最差复杂度:O(n2);平均复杂度:O(n2)

空间复杂度:O(1)

3.算法实现-Java

public int[] insertionSort(int[] arr){for(int i = 1; i < arr.length; i++){int preIndex = i - 1;int currentValue = arr[i];while(preIndex >= 0 && currentValue< arr[preIndex]){arr[preIndex + 1] = arr[preIndex];preIndex -= 1;}arr[preInde + 1] = currentValue;}return arr;
}

 

http://www.lryc.cn/news/110554.html

相关文章:

  • Centos虚拟机忘记密码-修改密码
  • Shell 分析服务器日志常用命令
  • mysql8配置binlog日志skip-log-bin,开启、关闭binlog,清理binlog日志文件
  • 机器学习:训练集与测试集分割train_test_split
  • 淘宝API开发(一)简单介绍淘宝API功能接口作用
  • Redis相关面试题
  • 数据库简介
  • 腾讯云国际轻量应用服务器怎么使用呢?
  • arm环境cloudstack在vpc下创建虚拟机失败
  • Linux上安装Keepalived,多台Nginx配置Keepalived(保姆级教程)
  • centos7 ‘xxx‘ is not in the sudoers file...
  • Zebec Payroll :计划推出 WageLink On-Demand Pay,进军薪酬发放领域
  • 【2023】字节跳动 10 日心动计划——第三关
  • 【无网络】win10更新后无法联网,有线无线都无法连接,且打开网络与Internet闪退
  • HTML <script> 标签
  • FPGA----UltraScale+系列的PS侧与PL侧通过AXI-HP交互(全网唯一最详)附带AXI4协议校验IP使用方法
  • Unity小游戏——迷你拼图
  • 三 动手学深度学习v2 —— Softmax回归+损失函数+图片分类数据集
  • Stable Diffusion 使用教程
  • 在线考试系统springboot学生试卷问答管理java jsp源代码mysql
  • 创建vue-cli(脚手架搭建)
  • 【单调栈part02】| 503.下一个更大元素||、42.接雨水
  • Java——如何使用Stream替换掉List<Student>中符合要求的元素
  • gin 框架中的 gin.Context
  • 新版chrome浏览器恢复下载的时候恢复底栏提示
  • ModuleNotFoundError: No module named ‘lsb_release‘
  • 2021-03-03 Multisim 14.0 电池充电防止反接保护
  • 【AI】《动手学-深度学习-PyTorch版》笔记(八):线性回归
  • uniapp 持续获取定位(登录状态下才获取)(不采用定时器)(任意页面都可监听定位改变)
  • 【Linux】Linux工具