java基础-冒泡排序以及稀疏数组

java基础

---

以下内容为本人的学习笔记，如需要转载，请声明原文链接   https://www.cnblogs.com/lyh1024/p/16720908.html

---

Ø 冒泡排序原理：

比较数组中，两个相邻的元素，如果第一个数比第二个数大，我们就交换他们的位置；
每一次比较，都会产生出一个最大，或者最小的数字；
下一轮则可以少一次排序；
依次循环，知道结束！

冒泡排序的时间复杂度为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+"\t");

            }

            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+"\t");

            }

            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 + "\t");

            }

            System.out.println();

        }

    }

}

java基础-冒泡排序以及稀疏数组的相关教程结束。