问题描述
利用插入排序把一列数组按从小到大或从大到小排序
(一)、插入排序思想
以从小到大为例：
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]+ " " ); |
(三)、完整代码
把上述代码整理一下
|
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]+ " " );
} } |
(四)、运行结果
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
原文链接：https://blog.csdn.net/m0_57060319/article/details/119620110