插入排序是一种简单直观的排序算法。 03插入排序.mp4

算法思路

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

从小到大的插入排序整个过程如图示:例如初始数列{5,2,4,6,1,3}
image.png比完一次之后还要接着与下一个比较
第一轮：从第二位置的2开始比较，比前面5小，交换位置。
第二轮：第三位置的4比前一位置的5小，交换位置，依次往前比较。
第三轮︰第四位置的6比前一位置的5大，无需交换位置。
第四轮﹔第五位置的1比前一位置的6小，交换位置，再依次往前比较。
第五轮：第六位置的3比前一位置的6小，交换位置，再依次往前比较。

代码实现

  1. public class InsertSort {
  2.     public static void main(String[] args){
  3.         int[] arr = {2,6,9,3,1,5,2,4};
  4.         insertSort(arr);
  5.         System.out.println(Arrays.toString(arr));
  6.     }
  8.     public static void swap(int[] arr,int i,int j)
  9.     {
  10.         int temp = arr[i];
  11.         arr[i] = arr[j];
  12.         arr[j] = temp;
  13.     }
  15.     public static void insertSort(int[] arr)
  16.     {
  17.         for(int i=1;i<arr.length;i++)
  18.         {
  19.             for(int j=i;j>0;j--)
  20.             {
  21.                 if(arr[j]<arr[j-1])
  22.                 {
  23.                     //交换位置
  24.                     swap(arr,j,j-1);
  25.                 }else{
  26.                     break;
  27.                 }
  28.             }
  29.         }
  30.     } 
  31. }

算法稳定性︰

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的;插入排序是稳定的排序算法。

时间复杂度∶O(n2)