Java实现插入排序

200 阅读 0 评论 132 点赞

我是靠谱客的博主细心墨镜，这篇文章主要介绍Java实现插入排序，现在分享给大家，希望可以做个参考。

问题描述

利用插入排序把一列数组按从小到大或从大到小排序

(一)、插入排序思想

以从小到大为例：

1、第一轮插入，从第二个数开始，与前面的数依次比较，遇到比自己小的数，就插入到该数后面的位置
2、第二轮插入，从第三个数开始，与前面的数依次比较，遇到比自己小的数，就插入到该数后面的位置
3、如此循环，直到所有数从小到大排列

(二)、问题分析

1. 输入数组

根据用户输入的进行排序的数字数量n，建立一个长度为n的数组

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
public static void main (String[] args){
  int n,m;
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入你想排序的数量n");
        n=sc.nextInt();
        
        int [] arrary = new int[n];
        System.out.println("请输入"+n+"个数，并用空格隔开");
        
        for(int i=0;i<arrary.length;i++){
            arrary[i]=sc.nextInt();
        }

2.输入如何排序

设置两条路径：m=1为从小到大，m=2为从大到小，m=其他提醒用户重新输入

复制代码

1
2
3
4
5
6
7
8
System.out.println("请问你想：1.从小到大 2.从大到小 排序？");
        m=sc.nextInt();

        while (m!=1 && m!=2 ){
            System.out.println("输入有误请再次输入");
            m = sc.nextInt();
            continue;
        }

3.排序算法

（1）数组长度 arrary.length 也就是用户输入的 n
（2）j 表示第 j 轮排序，这里面n-1轮排序就已足够
（3）k 表示第 k+1 个位置，arrary[k] 表示第 k+1 个位置的数
（4）每一轮的 k 从 j-1 开始，向前依次比较，每比较一次做一次k- -，直到遇到比该数小的数，则插入到这个较小数的后面
（5）上述想法可转换为：每一轮的 arrary[k+1] 与其前面比自己大的数交换位置，遇到比自己小的数则停止
（6）较大数与较小数交换位置的经典算法：若a>b; 则c=a; a=b; b=c;
（7）从大到小排序只需把 arrary[k]>arrary[k+1] 换成 arrary[k]<arrary[k+1] 即可
（8）选择进行何种排序，在 if 语句的判断框里加上此时m应该等于的值
（9）因为要先选择进行何种排序，才能进行排序，所以把 m==1 放在 arrary[k]>arrary[k+1] 前面，且用短板与 && ，这样更易于理解（如果m≠1，则直接进行else if 的语句）
（10）也可以 m==1 & arrary[k]>arrary[k+1] 或 arrary[k]>arrary[k+1] & m==1，但不能 arrary[k]<arrary[k+1] && m==2。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int j=1;j<arrary.length;j++){
            for (int k=j-1;k>=0;k--){
                if(m==1 && arrary[k+1]<arrary[k] ){
                    int a=arrary[k+1];
                    arrary[k+1]=arrary[k];
                    arrary[k]=a;
                }
                else if(m==2 && arrary[k]>arrary[k+1]){
                    int a=arrary[k+1];
                    arrary[k+1]=arrary[k];
                    arrary[k]=a;
                }

            }
        }

4.输出数组

由于输出的是一段数组，所以还需要引用一段 for 语句

复制代码

1
2
3
System.out.print("选择"+m+"的结果为：");
        for(int j=0;j<arrary.length;j++)
            System.out.print(arrary[j]+" ");

(三)、完整代码

把上述代码整理一下

复制代码

import java.util.Scanner;
public class Insertion {
    public static void main (String[] args){
        int n,m;
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入你想排序的数量n");
        n=sc.nextInt();

System.out.println("请问你想：1.从小到大 2.从大到小 排序？");
        m=sc.nextInt();

while (m!=1 && m!=2 ){
            System.out.println("输入有误请再次输入");
            m = sc.nextInt();
            continue;
        }

int [] arrary = new int[n];
        System.out.println("请输入"+n+"个数，并用空格隔开");
        for(int i=0;i<arrary.length;i++){
            arrary[i]=sc.nextInt();
        }

for (int j=1;j<arrary.length;j++){
            for (int k=j-1;k>=0;k--){
                if(m==1 && arrary[k+1]<arrary[k] ){
                    int a=arrary[k+1];
                    arrary[k+1]=arrary[k];
                    arrary[k]=a;
                }
                else if(m==2 && arrary[k]>arrary[k+1]){
                    int a=arrary[k+1];
                    arrary[k+1]=arrary[k];
                    arrary[k]=a;
                }

}
        }

System.out.print("选择"+m+"的结果为：");
        for(int j=0;j<arrary.length;j++)
            System.out.print(arrary[j]+" ");

}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
public class Insertion {
    public static void main (String[] args){
        int n,m;
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入你想排序的数量n");
        n=sc.nextInt();

        System.out.println("请问你想：1.从小到大 2.从大到小 排序？");
        m=sc.nextInt();

        while (m!=1 && m!=2 ){
            System.out.println("输入有误请再次输入");
            m = sc.nextInt();
            continue;
        }

        int [] arrary = new int[n];
        System.out.println("请输入"+n+"个数，并用空格隔开");
        for(int i=0;i<arrary.length;i++){
            arrary[i]=sc.nextInt();
        }

        for (int j=1;j<arrary.length;j++){
            for (int k=j-1;k>=0;k--){
                if(m==1 && arrary[k+1]<arrary[k] ){
                    int a=arrary[k+1];
                    arrary[k+1]=arrary[k];
                    arrary[k]=a;
                }
                else if(m==2 && arrary[k]>arrary[k+1]){
                    int a=arrary[k+1];
                    arrary[k+1]=arrary[k];
                    arrary[k]=a;
                }

            }
        }

        System.out.print("选择"+m+"的结果为：");
        for(int j=0;j<arrary.length;j++)
            System.out.print(arrary[j]+" ");

    }
}