利用数组实现直接插入排序

  假设待排序数据存放在数组A[1..n]中，则A[1]可看作是一个有序序列，让i从2开始，依次将A[i]插入到有序序列A[1..i-1]中，A[n]插入完毕则整个过程结束，A[1..n]成为有序序列。

排序过程示例  （用【】表示有序序列）

待排序数据：  【25】  54 8  54  21 1  97  2 73  15            （n=10）

i=2：                    【25 54】  8 54  21  1 97  2  73  15

i=3：                    【8  25  54】  54 21  1  97 2  73  15

i=4：                    【8 25  54 54】 21  1  97 2  73  15

i=5：                    【8 21 25  54  54】  1 97  2  73  15

i=6：                    【1  8  21 25  54  54】  97  2 73  15

i=7：                    【1 8  21  25 54  54 97】 2  73  15

i=8：                    【1 2 8  21  25 54  54  97】  73  15

i=9：                    【1 2  8  21 25  54  54 73  97】  15

i=10：                  【1 2  8 15  21 25  54  54 73  97】           排序结束

 

package repeat_job1; import java.util.Scanner; public class Str_Insert_Sort { public static void main(String[] args) { Scanner reader=new Scanner(System.in); System.out.println("请输入n："); int n=reader.nextInt(); int i,j,index=0,insert_num=0; int a[]=new int[n]; System.out.println("请输入数组元素："); for(i=0;i<n;i++) { a[i]=reader.nextInt(); } reader.close(); for(i=0;i<n-1;i++) { for(j=0;j<=i;j++) { if(a[j]>a[i+1]) { index=j; insert_num=a[i+1]; for(j=i+1;j>index;j--) { a[j]=a[j-1]; } a[index]=insert_num; } } } for(i=0;i<n;i++) { System.out.print(" "+a[i]); } } }

面向对象思想：

package repeat_job1; public class insert_Sort { private static int i,j; public insert_Sort(){} public static void str_Insert_Sort(int n,int []a) { int index=0,insert_num=0; for(i=0;i<n-1;i++) { for(j=0;j<=i;j++) { if(a[j]>a[i+1]) { index=j; insert_num=a[i+1]; for(j=i+1;j>index;j--) { a[j]=a[j-1]; } a[index]=insert_num; } } } } }

 

import java.util.Scanner; import repeat_job1.insert_Sort; public class Test4 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner reader=new Scanner(System.in); System.out.println("请输入n："); int n=reader.nextInt(); int i; int a[]=new int[n]; System.out.println("请输入数组元素："); for(i=0;i<n;i++) { a[i]=reader.nextInt(); } reader.close(); insert_Sort.str_Insert_Sort(n, a);//直接插入排序你 for(i=0;i<n;i++) { System.out.print(" "+a[i]); } } }

 

转载于:https://www.cnblogs.com/zyh2017/p/5001731.html