直接插入排序

思想：插入排序就是要每一轮排序都要将当前元素插入到一个已经有序的数组中。将当前元素和有序数组的最后一个元素进行比较

  • 如果当前元素大于最后一个元素，笔试直接放入有序数组的后面即可，然后接着往后取元素执行插入排序
  • 如果当前元素小于最后一个元素，则执行交换操作，然后继续往前比较，直到无法进行交换操作或是到达有序数组的起始位置。
    直接插入排序 - 图1

时间复杂度：

当前元素的选择次数为数组的长度为
直接插入排序 - 图2直接插入排序 - 图3%20%3D%20O(N)#card=math&code=O%28N%20%2A%201%29%20%3D%20O%28N%29)直接插入排序 - 图4%20%3DO(N%5E2)#card=math&code=O%28N%20%2A%20N%29%20%3DO%28N%5E2%29)直接插入排序 - 图5#card=math&code=O%28N%5E2%29)

空间复杂度：

由于排序过程直接在原数组上进行操作，并没有申请额外的空间，所以为
直接插入排序 - 图6#card=math&code=O%281%29)

稳定性：

从排序的过程可以看出，如果存在两个相等元素，插入的过程不改变两个元素的相对位置。因此直接插入排序是一种稳定的排序算法

Java代码实现：

  1. public int[] insertSort(int[] arr){
  2.     if(arr.length  < 2){
  3.         return arr;
  4.     }
  6.     for (int i = 0; i < arr.length; i++) {
  7.         int index = i;
  8.         System.out.print(arr[i] + " " );
  9.         while (index > 0){
  10.             if(arr[index] < arr[index-1]){
  11.                 swap(arr, index, index - 1);
  12.                 index--;
  13.             }else{
  14.                 break;
  15.             }
  16.         }
  17.         System.out.println(Arrays.toString(arr));
  18.     }
  19.     return arr;
  20. }
  22. public void swap(int[] arr, int i, int j) {
  23.     int temp = arr[i];
  24.     arr[i] = arr[j];
  25.     arr[j] = temp;
  26. }

Python代码实现：

  1. # 插入排序
  2. def insert_sort(nums):
  3.     # 起始将索引为0的位置当作有序序列，所以我们实际上只需要做 n - 1 次插入排序
  4.     for i in range(0, len(nums) - 1):
  5.         while i > 0:
  6.             # 然后将无序序列的第一个元素插入到有序序列的合适位置
  7.             if nums[i] < nums[i - 1]:
  8.                 nums[i], nums[i - 1] = nums[i - 1], nums[i]
  9.                 i -= 1
  10.             # 当前元素正好放入有序序列最后的位置，则不执行交换操作，访问下一个元素
  11.             else:
  12.                 break
  13.         print('index: {} -- {}'.format(i, nums))
  15.     return nums
  17. if __name__ == "__main__":
  18.     nums = [5, 2, 9, 7, 6, 12, 3, 4]
  20.     # 插入排序
  21.     print('insert sort result is: ', insert_sort(nums))