数据结构之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));
         }
        }