資料結構之Java實作兩個隨機陣列合并進行排序

原文地址：www.dushunchang.top

前言：

? 小Du猿結束"996ICP"CRUD開發作業生活，重新進入了校園學習生活，本周開始了第二周資料結構的基礎知識學習，大愛向宇老師的上課方式，用生動形象的方式講解抽象概念，但一開口就是LSP.O(∩_∩)O，向向宇大佬致敬，菜雞小Du猿投來膜拜的眼光，

? 此博客用Java實作線性表的思想，實作陣列的排序和序列化，序列化的排序方式采用冒泡排序的方式，但小Du猿正在優化該演算法，原因為：采用冒泡排序的方式時間復雜度較大，正在考慮使用快速排序法；但此篇博客使用冒泡排序的方式，便于理解概念，

一、什么是線性表

• Q1：什么是線性表：

  A1：線性表是由N個型別相同的資料元素的有限序列（換句話描述：是具有像線一樣的性質的表）

  ---

• Q2: 線性表的順序存盤結構:

• A2: 一段地址連續的存盤單元依次存盤線性表的資料元素，使得線性表中在邏輯結構上相鄰的資料元素存盤在連續的物理存盤單元中，

  ---

• Q3：線性表的優缺點：

• A3：

  • 優點：1.無須為表示表中元素之間的邏輯關系而增加額外的存盤空間，

    ? 2. 可以快速地存取表中任一位置的元素，

  • 缺點：1.插入和洗掉操作需要移動大量元素，

    ? 2.當線性表長度變化較大時，難以確定存盤空間的容量，
    ? 3.造成存盤空間的“碎片”，

    ---

二、ArrayList集合

? 上課時理解線性表的基本概念后，我不禁想到了"ArrayList"集合，而ArrayList的特征基本與線性表大致符合，所以我在此梳理一下ArrayList的概念：

• ArrayList的底層是Object類的陣列，默認長度是10,超過10后，長度變為原長度的1.5倍，

• 可以簡單的認為是一個動態陣列；實際上ArrayList就是用陣列實作的，長度不夠時，呼叫Arrays.copyOf方法，拷貝當前陣列到一個新的長度更大的陣列，

特點：

• 隨機訪問速度快，插入和移除性能較差(陣列的特點)；

• 支持null元素的存在；

• 有順序結構；

• 元素可以重復；

• 但執行緒不安全，

梳理ArrayList集合后，我們可以大概將線性表的特征約等于ArrayList集合，頓時小Du猿"悟了"?(? ???ω??? ?)?

三、用線性表的思想排序陣列間排序

實作的原理小Du用圖的方式整理出來：

代碼如下：

package com.company;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Du Shun Chang
 * @version 1.0
 * @date 2021/9/7 22:48
 * @Todo: 1.隨機產生兩個陣列，并進行兩個陣列的排序，2.排序好的陣列，進行排序合并
 * @QQ:1300442386
 */
public class Mian {
    public static void main(String[] args) {
        
//初始化兩個長度為10的陣列
        Random random = new Random();
        int[] a = new int[10];
        int[] b = new int[10];
//隨機生成1000以內的數，并賦值到陣列中
        for (int i = 0; i < 10; i++) {
            a[i] = random.nextInt(1000);
            b[i] = random.nextInt(1000);
        }
        System.out.println("隨機產生陣列A：" + Arrays.toString(a));
        System.out.println("隨機產生陣列B：" + Arrays.toString(b));
        int temp = 0;
//重新排序隨機陣列A
        for (int i = 0; i < 10; i++) {
            for (int j = i; j < 10; j++) {
                if (a[i] >= a[j]) {
                    // 定義中間變數值
                    temp = a[i];
                    // 換位賦值
                    a[i] = a[j];
                    // 獲得新位置
                    a[j] = temp;
                }
            }
        }
        System.out.println("排序后的陣列A：" + Arrays.toString(a));
//重新排序隨機陣列B
        for (int i = 0; i < 10; i++) {
            for (int j = i; j < 10; j++) {
                if (b[i] >= b[j]) {
                    // 定義中間變數值
                    temp = b[i];
                    // 換位賦值
                    b[i] = b[j];
                    // 獲得新位置
                    b[j] = temp;
                }
            }
        }
        System.out.println("排序后的陣列B：" + Arrays.toString(b));
//對新的陣列進行合并及進行排序
        int l = a.length + b.length;
        int[] temps = new int[l];
        int i = 0, j = 0, h = 0;
        while (i < a.length || j < b.length) {
            if (i == a.length && j < b.length) {
                temps[h++] = b[j++];
            } else if (i < a.length && j == b.length) {
                temps[h++] = a[i++];
            } else if (a[i] <= b[j]) {
                temps[h++] = a[i++];
            } else if (a[i] > b[j]) {
                temps[h++] = b[j++];
            }
        }
        System.out.print("排序后最新陣列：" + Arrays.toString(temps));
    }
}

運行結果為：

四、冒泡排序：

冒泡排序：
在陣列中兩兩進行比較，較大數往后移動，與下一位數再次兩兩比較，依次回圈排序，
原理圖如下：
代碼如下：

/**
 * @author Du Shun Chang
 * @version 1.0
 * @date 2021/9/8 22:48
 * @Todo: 冒泡排序演示
 * @QQ:1300442386
 */
 public class Mian{
    public static void main(String[] args) {
   int[] arr = {6, 3, 8, 2, 9, 1};
        System.out.println("排序前陣列為：" + Arrays.toString(arr));
        for (int s = 0; s < arr.length - 1; s++) {//外層回圈控制排序趟數
            for (int k = 0; k < arr.length - 1 - s; k++) {//內層回圈控制每一趟排序多少次
                if (arr[k] > arr[k + 1]) {
                    int temp1 = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp1;
                }
            }
        }
        System.out.println("排序后陣列為：" + Arrays.toString(arr));
         }
        }

結果為：

前路漫漫，我禿了，也強了，覺得不錯，一波三聯，您的肯定就是小Du猿最大的動力，Thanks?(･ω･)ﾉ

?