Java算法入门

矫情吗；* 2023-01-01 05:55 115阅读 0赞

### Java算法入门 ###

**插入排序**

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

基本思想：

把n个待排序的元素看成一个有序表和一个无需表，开始的时候有序表只有1个元素，无序表中有n-1个元素；

每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

代码如下：

public class InsertSort \{

public static void getInsertSort(int\[\] a) \{

if(a == null || a.length == 0) \{//判断数组是否为空

System.out.println("该数组为空！");

return;

int n = a.length;//将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能

int temp;//放于for循环外面是为了防止重复创建变量

int j;

for(int i = 1; i < n;i++)\{//排序的趟数

temp = a\[i\];//赋给temp是为了防止索引i之前的元素向后移动覆盖了索引i的元素

j = i-1;

for(; j>=0&&a\[j\]>temp; --j) \{//将大于i位置元素的元素向后移

a\[j+1\] = a\[j\];

a\[j+1\]= temp;//找到i应该在的位置，将值放置此处

public static void main(String\[\] args) \{

int\[\] a = \{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34\};

getInsertSort(a);

System.out.print("直接插入排序：");

for(int i = 0; i < a.length; i++) \{

System.out.print(a\[i\] + " ");

运行之，输出结果：

直接插入排序：1 2 3 3 4 5 6 7 11 23 34 44 23

十大经典排序算法最强总结（含JAVA代码实现）

[https://www.cnblogs.com/guoyaohua/p/8600214.html][https_www.cnblogs.com_guoyaohua_p_8600214.html]

**Java单链表的实现**

什么是单链表

单链表是链表的其中一种基本结构。一个最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70][]

【单链表中三个概念需要区分清楚：分别是头指针，头节点和首元节点。

头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

![20201231165744815.png][]

头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

单链表中可以没有头结点，但是不能没有头指针！ 头节点的引入能使链表对第一个元素的删除和插入和其他元素相同，不用另外说明，使得代码更加简洁。】

单链表的基本操作有：增（add)，删(remove)，改(set)，查（find)，插(insert)等。

**单链表增添元素**

1.  声明一个新节点node作为新的尾节点，next=null;
2.  获取原链表的最后一个节点，把它的next指向1步骤的新节点node
3.  记录链表长度的变量+1

**单链表删除元素**

1.  获取需要删除的节点的上一个节点node
2.  把node的next指向node的next的next
3.  因为node的next节点没有指针指向它，因此它会被系统自动清理
4.  记录链表长度的变量-1

**单链表插入元素**

1.  获取需要插入的位置的节点；
2.  声明一个新节点node指向1步骤得到的节点；
3.  获取需要插入位置节点的上一个节点；
4.  将3步骤得到的节点的next指向新节点node；
5.  记录链表长度的变量+1。

Java单链表的简单操作实现

1.  **定义结点类代码如下**

package listTestPack;  
//定义结点类  
public class Node \{  
    private int data;  
    public Node next;  
    public Node(int data) \{  
        this.data = data;  
    \}  
       
    public int getData() \{  
        return data;  
    \}  
   
    public void setData(int data) \{  
        this.data = data;  
    \}  
   
    public void display() \{  
        System.out.println("data="+data);  
           
    \}  
       
\}

**2）定义链表操作类代码如下**

package listTestPack;  
//定义链表操作类  
public class LinkList \{  
    //构造头结点  
    private Node first;  
    //记录结点位置  
    private int pos=0;  
       
    public LinkList() \{  
        this.first=null;  
    \}  
    /\*\*  
     \* 插入一个头结点  
     \*/  
    public void input(int data) \{  
        Node node=new Node(data);  
        node.next=first;  
        first=node;  
    \}  
    /\*  
     \* 删除头结点 并返回头结点  
     \*/  
    public Node delete() \{  
        Node tmpeNode=first;  
        first =tmpeNode.next;  
        return first;  
    \}  
    /\*  
     \* 在任意位置添加结点  
     \*/  
public void addList(int i,int data) \{  
    Node node=new Node(data);  
    Node useNode=first;  
    Node preNode=first;  
    while (i!=pos) \{  
        preNode=useNode;  
        useNode=useNode.next;  
        pos++;  
    \}  
       
    node.next=useNode;  
    preNode.next=node;  
    pos=0;  
\}  
/\*  
 \* 在任意位置删除结点  
 \*/  
public Node delete(int i) \{  
    Node preNode=first;  
    Node useNode = first;  
    if(first==null) \{  
        return first;  
    \}  
    while(i!=pos) \{  
        preNode=useNode;  
        useNode=useNode.next;  
        pos++;  
    \}  
    preNode.next=useNode.next;  
    pos=0;  
    return useNode;  
\}  
/\*  
 \* 头插法建立链表  
 \*/  
public void Initlist(int a\[\]) \{  
    for (int i = 0; i < a.length; i++) \{  
        Node node=new Node(a\[i\]);  
        node.next=first;  
        first=node;  
    \}  
\}  
/\*  
 \* 尾插法建链表  
 \*/  
public void InitList2(int a\[\]) \{  
    Node qNode=first;  
    for (int i = 0; i < a.length; i++) \{  
        Node node=new Node(a\[i\]);  
        qNode.next=node;  
        qNode=node;  
    \}  
   
\}  
/\*  
 \* 查询结点信息为data的位置  
 \*/  
public int findList(int data) \{  
    Node useNode=first;  
    if(first==null) \{  
        System.out.println("该链表为空！");  
        return 0;  
    \}  
    while(useNode.getData()!=data) \{  
        useNode=useNode.next;  
        pos++;  
    \}  
    int i=pos;  
    pos=0;  
    System.out.println("该元素在第"+i+"位置");  
    return i;  
\}  
/\*  
 \* 显示链表中的结点信息  
 \*/  
public void displayall() \{  
    Node useNode=first;  
    while(useNode!=null) \{  
        useNode.display();  
        useNode=useNode.next;  
    \}  
    System.out.println();  
    \}  
\}

**3）测试类代码如下：**

package listTestPack;  
//测试类  
public class listTest \{  
    public static void main(String\[\] args) \{  
        // TODO Auto-generated method stub  
        LinkList laLinkList=new LinkList();  
        //检验插入头结点  
        laLinkList.input(10);  
        laLinkList.input(20);  
        laLinkList.input(30);  
        System.out.println("显示插入的三个头结点元素");  
        laLinkList.displayall();  
        //检验任意位置插入结点  
        laLinkList.addList(1, 1);  
        laLinkList.addList(2, 2);  
        laLinkList.addList(3, 3);  
        System.out.println("显示任意位置插入元素的值");  
        //显示结点信息  
        laLinkList.displayall();  
        //删除值为2的结点  
        System.out.println("显示删除功能");  
        Node deleNode=laLinkList.delete(2);  
        System.out.println("===============");  
        //显示删除结点的信息  
        deleNode.display();  
        System.out.println("=============");  
        //显示全部信息  
        laLinkList.displayall();  
        System.out.println("---------------------");  
        System.out.println("下面是查询");  
        //查询元素为3的位置  
        laLinkList.findList(3);  
        System.out.println("---------------------");  
        int a\[\]= \{1,2,3,4,5\};  
        LinkList laLinkList2=new LinkList();  
        //头插法建链表  
        System.out.println("下面是头插法建链表");  
        laLinkList2.Initlist(a);  
        laLinkList2.displayall();  
   
        System.out.println("下面是尾插法");  
        LinkList laLinkList3=new LinkList();  
        //先插入一个头结点  
        laLinkList3.input(0);  
        laLinkList3.InitList2(a);  
        laLinkList3.displayall();  
        //Node n1=new Node(20);  
        //n1.display();  
     \}  
\}

**4)使用bluej运行测试**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1][]

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 2][]

最后，给出实现等腰三角形、直角三角形、菱形代码

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 3][]

☆等腰三角形Isosceles Triangle

public class IsoscelesTriangle \{

public static void main(String\[\] args)\{

for(int i=1;i<=6;i++)\{

for(int j =6;j>i;j--)\{

System.out.print(" ");

for(int j=1;j<=2\*i-1;j++)\{

System.out.print("\*");

System.out.println();

☆直角三角形Right Triangle

public class RightTriangle\{

public static void main(String\[\] args)\{

for(int i=1; i<=6; i++)\{

for(int j=1;j<=i;j++)\{

System.out.print("\*");

System.out.println();

☆打印一个菱形Rhombus

public class Rhombus\{

public static void main(String\[\] args)\{

for(int i=0;i<6;i++)\{

for(int j=5;j>i;j--)\{

System.out.print(" ");

for(int j=0;j<2\*i+1;j++)\{

System.out.print("\*");

System.out.println();

for(int i=0;i<6;i++)\{

for(int j=0;j<=i;j++)\{

System.out.print(" ");

for(int j=10;j>i\*2+1;j--)\{

System.out.print("\*");

System.out.println();

附录、

Java基础--单链表的实现

[https://blog.csdn.net/weixin\_36605200/article/details/88804537][https_blog.csdn.net_weixin_36605200_article_details_88804537]

[https_www.cnblogs.com_guoyaohua_p_8600214.html]: https://www.cnblogs.com/guoyaohua/p/8600214.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70]: /images/20221120/588561ee99f84aeab52e4d9cc4fffac5.png
[20201231165744815.png]: /images/20221120/b0047e457d9548198630de49e61bd5c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1]: /images/20221120/d2a3c718196643d2ab858a3f6c2118b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 2]: /images/20221120/6b3d707970b4411daaf8f900be4ab7a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 3]: /images/20221120/6c7c5d9770e14373a815a1e5b9fd50a0.png
[https_blog.csdn.net_weixin_36605200_article_details_88804537]: https://blog.csdn.net/weixin_36605200/article/details/88804537