java基础-冒泡排序以及稀疏数组
2023-03-31 10:46:12 时间
以下为本人的学习笔记
Ø 冒泡排序原理:
- 比较数组中,两个相邻的元素,如果第一个数比第二个数大,我们就交换他们的位置;
- 每一次比较,都会产生出一个最大,或者最小的数字;
- 下一轮则可以少一次排序;
- 依次循环,直到结束!
冒泡排序的时间复杂度为O(n²)。
- 代码:
import java.util.Arrays; public class SortTest { public static void main(String[] args) { int[] list1 = {1,33,25,6,4,64,6,99,7,93,44}; int[] list2 = sort(list1); System.out.println(Arrays.toString(list2)); } public static int[] sort(int[] list){ int temp = 0;
//外层循环判断走多少次 for (int i =0;i<list.length-1;i++){
//内层循环,比较判断两个数,如果第一个数比第二个数大,这两个数就交换位置 for (int j = 0 ; j < list.length-1-i;j++){ if (list[j] > list[j+1]){ temp = list[j]; list[j] = list[j+1]; list[j+1] = temp; } } } return list; } }
注意:Arrays.toString()用来输出数组元素转字符串
Ø 使用稀疏数组的条件:
当一个数组中大部分都是0,或者为同一值的数组时,可以使用稀疏数组来保存该数组。
Ø 稀疏数组原理:
- 记录数组的行数和列数,以及不同值的个数;
- 把具有不同值的元素和行列及值记录在一个小规模的数组中,从而缩小程序的规模
- 代码:
public class SortTest { public static void main(String[] args) { //1、创建一个二维数组11*11 int[][] list1 = new int[11][11]; list1[1][2] = 1; list1[2][3] = 2; System.out.println("输入原始数组..."); for (int[] ints : list1) { for (int anInt : ints) { System.out.print(anInt+" "); } System.out.println(); }
System.out.println("----------------------------------------------------"); //转换 为稀疏数组保存 //获取有效值的个数 int sum = 0; for (int i=0;i<list1.length;i++){ for (int j = 0;j<list1.length;j++){ if (list1[i][j] != 0 ){ sum++; } } } System.out.println("list1 的元素有:"+ sum+"个"); //1、创建一个稀疏数组的数组 int[][] list2 = new int[sum+1][3]; list2[0][0] = 11; list2[0][1] = 11; list2[0][2] = sum; //2、遍历一个二维数组,将非零的值,存放在稀疏数组中 int count = 0 ; for (int i = 1;i<list1.length;i++){ for (int j = 0;j<list1.length;j++){ if (list1[i][j] != 0 ) { count++; list2[i][0] = i; list2[i][1] = j; list2[i][2] = list1[i][j]; } } } System.out.println("输入稀疏数组..."); for (int[] ins:list2){ for(int anInt: ins){ System.out.print(anInt+" "); } System.out.println(); }
System.out.println("--------------------------------------------------"); //1、读取稀疏数组 int[][] list3 = new int[list2[0][0]][list2[0][1]]; //2、还原稀疏数组 for (int i =1 ; i<list2.length;i++) { list3[list2[i][0]][list2[i][1]] = list2[i][2]; } //3、打印 System.out.println("输出还原的数组"); for (int[] ints:list3){ for (int anInt:ints){ System.out.print(anInt + " "); } System.out.println(); } } }
相关文章
- 修改第三方jar包里的类的方法
- JVM垃圾回收机制
- Java中的静态代理和动态代理
- 32位eclipse怎么安装?
- 32位eclipse能用64位jdk吗?
- LeetCode笔记:141. Linked List Cycle
- Flink重点难点:Flink任务综合调优(Checkpoint/反压/内存)
- Java Review - 并发编程_前置知识二
- Java解惑五:类之谜
- Maven 依赖调解源码解析(六):dependencyManagement 版本锁定
- Maven 依赖调解源码解析(五):同一个文件内声明,后者覆盖前者
- Maven 依赖调解源码解析(四):传递依赖,第一声明者优先
- Maven 依赖调解源码解析(三):传递依赖,路径最近者优先
- Maven 依赖调解源码解析(二):如何调试 Maven 源码和插件源码
- Maven 依赖调解源码解析(一):开篇
- jenkens2权威指南
- Java的脚本机制、编译器API
- Java 定时任务
- Java 中的屠龙之术:如何修改语法树?
- 并发编程系列之volatile关键字详解