Jva培训之插入排序法

  思想:插入排序法的排序思想就是从数组的第二个元素开始,将数组中的每一个元素按照规则插入到已排好序的数组中以达到排序的目的.一般情况下将数组的第一个元素作为启始元素,从第二个元素开始依次插入.由于要插入到的数组是已经排好序的,所以只是要从右向左找到比插入点(下面程序中的insertNote)小(对升序而言)的第一个数组元素就插入到其后面.直到将最后一个数组元素插入到数组中,整个排序过程就算完成.
    稳定性:稳定的.
    时间复杂度:O(n²)
    实例:
import java.util.*;
class sorts
{
 public static void main(String[] args)
 {
  int[] arr= new int[]{800,9,3,6,12,54,35,411,3,245,1,0,4};
  sorts.InsertSort(arr);
 }
 public static int[] InsertSort(int[] arr)
 {
  int i,j;
  int insertNote;//要插入的数据
  int[] array=arr;
    
   //从数组的第二个元素开始循环将数组中的元素插入
  for (i=1;i<array.length;i++)
  {
   //设置数组中的第2个元素为第一次循环要播讲的数据
   insertNote = array[i];
   j=i-1;
   while(j>=0&&insertNote<array[j])   
   {
    //如果要播讲的元素小于第j个元素,就将第j个元素向后移动
    array[j+1]=array[j];
    j–;
   }
   //直到要插入的元素不小于第j个元素,将insertNote插入到数组中
   array[j+1]=insertNote; 
  }
  //打印排序后的数组
  System.out.println(Arrays.toString(array));
  return array;
  
 }
}