java基礎-冒泡排序以及稀疏數組

 以下內容為本人的學習筆記，如需要轉載，請聲明原文鏈接   https://www.cnblogs.com/lyh1024/p/16720908.html

Ø 冒泡排序原理：

1. 比較數組中，兩個相鄰的元素，如果第一個數比第二個數大，我們就交換他們的位置；
2. 每一次比較，都會產生出一個最大，或者最小的數字；
3. 下一輪則可以少一次排序；
4. 依次迴圈，知道結束！

 冒泡排序的時間複雜度為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();
          }
      }
  }