Java實現(xiàn)插入排序

更新時間：2021年08月27日 09:09:28 作者：這個對數(shù)不太對

這篇文章主要介紹了Java實現(xiàn)插入排序，把一列數(shù)組按從小到大或從大到小排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

問題描述

利用插入排序把一列數(shù)組按從小到大或從大到小排序

(一)、插入排序思想

以從小到大為例：

1、第一輪插入，從第二個數(shù)開始，與前面的數(shù)依次比較，遇到比自己小的數(shù)，就插入到該數(shù)后面的位置
2、第二輪插入，從第三個數(shù)開始，與前面的數(shù)依次比較，遇到比自己小的數(shù)，就插入到該數(shù)后面的位置
3、如此循環(huán)，直到所有數(shù)從小到大排列

(二)、問題分析

1. 輸入數(shù)組

根據(jù)用戶輸入的進(jìn)行排序的數(shù)字?jǐn)?shù)量n，建立一個長度為n的數(shù)組

public static void main (String[] args){
  int n,m;
        Scanner sc = new Scanner(System.in);
        System.out.println("請輸入你想排序的數(shù)量n");
        n=sc.nextInt();
        
        int [] arrary = new int[n];
        System.out.println("請輸入"+n+"個數(shù)，并用空格隔開");
        
        for(int i=0;i<arrary.length;i++){
            arrary[i]=sc.nextInt();
        }

2.輸入如何排序

設(shè)置兩條路徑：m=1為從小到大，m=2為從大到小，m=其他提醒用戶重新輸入

System.out.println("請問你想：1.從小到大 2.從大到小 排序？");
        m=sc.nextInt();

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

3.排序算法

（1）數(shù)組長度 arrary.length 也就是用戶輸入的 n
（2）j 表示第 j 輪排序，這里面n-1輪排序就已足夠
（3）k 表示第 k+1 個位置，arrary[k] 表示第 k+1 個位置的數(shù)
（4）每一輪的 k 從 j-1 開始，向前依次比較，每比較一次做一次k- -，直到遇到比該數(shù)小的數(shù)，則插入到這個較小數(shù)的后面
（5）上述想法可轉(zhuǎn)換為：每一輪的 arrary[k+1] 與其前面比自己大的數(shù)交換位置，遇到比自己小的數(shù)則停止
（6）較大數(shù)與較小數(shù)交換位置的經(jīng)典算法：若a>b; 則c=a; a=b; b=c;
（7）從大到小排序只需把 arrary[k]>arrary[k+1] 換成 arrary[k]<arrary[k+1] 即可
（8）選擇進(jìn)行何種排序，在 if 語句的判斷框里加上此時m應(yīng)該等于的值
（9）因為要先選擇進(jìn)行何種排序，才能進(jìn)行排序，所以把 m==1 放在 arrary[k]>arrary[k+1] 前面，且用短板與 && ，這樣更易于理解（如果m≠1，則直接進(jìn)行else if 的語句）
（10）也可以 m==1 & arrary[k]>arrary[k+1] 或 arrary[k]>arrary[k+1] & m==1，但不能 arrary[k]<arrary[k+1] && m==2。

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.輸出數(shù)組

由于輸出的是一段數(shù)組，所以還需要引用一段 for 語句

System.out.print("選擇"+m+"的結(jié)果為：");
        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("請輸入你想排序的數(shù)量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+"個數(shù)，并用空格隔開");
        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+"的結(jié)果為：");
        for(int j=0;j<arrary.length;j++)
            System.out.print(arrary[j]+" ");

    }
}