几大排序算法之直接插入排序（Java实现）

直接插入排序

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

public static void insertionSort(int []arr){

        /*错误解答，虽然能实现结果，但是
                  {temp=arr[a];
                  arr[a]=arr[j];
                  arr[j]=temp;
                  a--;}
                  部分还是基于交换排序的

        int temp=0;
        for (int i=1;i<arr.length;i++){
              int a=i;
              for (int j=i-1;j>=0;j--){
                  if (arr[a]>=arr[j]){
                      break;
                  }
                  temp=arr[a];
                  arr[a]=arr[j];
                  arr[j]=temp;
                  a--;
              }
        }*/
        
        //可以修改为如下代码
        int temp=0;
        for (int i=1;i<arr.length;i++){
              int a=i;      //定义a，表示欲插入数的位置
              for (int j=i-1;j>=0;j--){
                  //如果欲插入数比他前面那个数大或相等，则退出循环
                  if (arr[i]>=arr[j]){  
                      break;
                  }
                  arr[a]=arr[j]; //将欲插入数前一个数后移一位
                  a--;
              }
              arr[a]=arr[i]; //将欲插入数arr[i]插入正确位置
        }        
    }

此处提供一个更简洁的实现方式

public static void insertionSort(int []arr){
       
        for(int i = 1; i<arr.length;i++)
        {
            //插入的数
            int insertVal = arr[i];
            //被插入的位置(准备和前一个数比较)
            int index = i-1;
            //如果插入的数比被插入的数小
            while(index>=0&&insertVal<arr[index])
            {
                //将把 arr[index] 向后移动
                arr[index+1]=arr[index];
                //让 index 向前移动
                index--;
            }
            //把插入的数放入合适位置
            arr[index+1]=insertVal;
        }
}