算法之插入排序

---

• 一：基本概念

  插入排序(Insert Sort)，每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

• 二：图文说明

插入排序示意图.png

我们分析一下排序具体过程：
1. 我们先假设数组下标为0的数据是排好序的，即38是排好序的；{38}
2. 取出数组下标为1的数据10，因为10<38,所以将10放在38前面；{10,38}
3. 取出数组下标为2的数据97，因为97>38,所以不进行排序，直接插入；{10,38,97}
4. 取出数组下标为3的数据76，因为98>76>38,所以将76放在38后面97前面；{10,38,76,97}
5. 取出数组下标为4的数据13，因为38>13>10,所以将13放在10后面38前面；{10,13,38,76,97}

即得排序完之后的升序结果！

• 三：代码实现

  1. C语言实现

  #include <stdio.h>
  /*
      插入排序 
  */
  
  void show(int arr[],int len);
  void insertSort(int arr[],int len); 
  void swap(int arr[],int i,int j);
  
  int main(void)
  {
      int arr[] = {38,10,97,76,13};
      int len = sizeof(arr)/sizeof(*arr);
      printf("待排序数组为:\n");
      show(arr,len);
      insertSort(arr,len);
      printf("排序之后的数组为:\n");
      show(arr,len);
      return 0;
  }
  
  void show(int arr[],int len)
  {
      int i;
      for(i=0;i<len;i++)
      {
          printf("%d ",arr[i]);
      }
      printf("\n");
  }
  
  void insertSort(int arr[],int len)
  {
      int i=0;
      int j=0;
      int temp = -1;
      int k = -1;
      for(i=1;i<len;i++)
      {
          k=i;
          temp = arr[k];
          
          for(j=i-1; (j>=0) && (arr[j]>temp); j--)
          {
              arr[j+1] = arr[j];
              k = j;
          }
          arr[k] = temp;
      }
  }
  
  void swap(int arr[],int i,int j)
  {
      int temp;
      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
  

  2.JAVA实现

  package com.data;
  import java.util.Arrays;
  /**
   * @author mxf
   * 插入排序
   */
  public class InsertSort {
      
      public static void main(String[] args) {
          int a[] = {38,10,97,76,13 };
          System.out.println("排序前的数组为:"+Arrays.toString(a));
          insertSort(a);
          System.out.println("排序后的数组为:"+Arrays.toString(a));
      }
      
      public static void insertSort(int[] arr){
          int i,j;
          int n = arr.length;
          int target;       //待插入的元素
          for(i = 1;i < n;i++){//默认第一个元素有序，直接从第二个元素开始进行插入
              j = i;
              target = arr[i];
              while(j>0 && target<arr[j-1]){//如果要插入的数据小于第j-1个元素则将第j-1个元素后移,找比target大的数字
                  arr[j] = arr[j-1];
                  j--;//将target元素依次和前面的所有数进行比较
              }
              arr[j] = target;
          }
      }
  }
  

• 四：插入排序的时间复杂度和稳定性

  1. 插入排序的时间复杂度
  • 插入排序是通过将当前第i个待排元素i与数组中前i-1个已经有序的元素j 进行两两比较，如果元素 i 小于 j，便交换。直到遇到比i小的元素或者到达数组头。由于每一个元素的插入都会最多比较i - 1次，因此最坏的时间复杂度为 1 + 2 + 3 + ... + n - 1 = n * (n - 1) / 2 ， 因此时间复杂度也为O(n*n)。
  2. 插入排序稳定性
  • 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，也就是第一个元素（默认它有序）。比较是从有序序列的末尾开始，也就是把待插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面。否则一直往前找直到找到它该插入的位置。如果遇见一个与插入元素相等的，那么把待插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序仍是排好序后的顺序，所以插入排序是稳定的。