插入排序算法—直接插入排序

算法思路：假定这些数字的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.

package test;

import java.util.Scanner;

public class InserSort {
 
 public static void main(String[] args) {
  
  /*输入十个数字*/
        int a[]=new int[10];
        Scanner sc=new Scanner(System.in);
        System.out.println(“请输入十个数字：”);
        for(int i=0;i<10;i++){
         a[i]=sc.nextInt();
        }
 
       /*排序的算法实现*/
       
  for(int i=1;i<10;i++){
   int j=i-1;
   int k=a[i];
   while(true){
    if(a[j]>k){
     a[j+1]=a[j];
     j–;
     if(j==-1)
      break;
    }
    else
     break;
   }
      a[j+1]=k;
  }
 //输出十个数字
     System.out.println(“从小到大的排序为:”);
 
     for(int i=0;i<10;i++){
      System.out.println(a[i]);
     } 
 }
}

插入排序时间复杂度：平均时间复杂度为O(n^2)最好情况:比较n-1次，最坏情况比较n(n-1)/2

稳定性:相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。