插入排序

分类：

比较类-交换排序

定义：简单直观

Insertion sort。也被称为直接插入排序。基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。对于一个数组A[0,n]的排序问题，假设认为数组在A[0,n-1]排序的问题已经解决了。
考虑A[n]的值，从右向左扫描有序数组A[0,n-1]，直到第一个小于等于A[n]的元素，将A[n]插在这个元素的后面。

难度：

简单

步骤：

• 建立一个哨兵（即临时变量），把要插入的数据赋给它。
• 插入数据从后面开始比较，如果大于前面的就记录下标，并将数据后移，直到插入数据碰到比它小的。
• 将临时变量赋值给当前记录下标。
• for循环即完成全部数据插入。

演示：

代码实现(javascript)：

function insertionSort(arr) {
    var len = arr.length;
    for (var i = 1; i < len; i++) {
        var j = i - 1;
        var temp = arr[i];
        while( j >= 0 && arr[j] > temp) {
             arr[j + 1] = arr[j];   // 将大于 temp(array[i]) 的数据后移
             j -= 1;   // 向前比较
        }
        arr[j + 1] = temp;
    }
    return arr;
}

python:
python 缩进一次是两个空格
&& -> and
|| -> or
for -> for... in...

def insertionSort(arr):
  print(arr)
  for i in range(1, len(arr)):
    j = i - 1
    tmp = arr[i]
    while j >= 0 and arr[j] > tmp:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = tmp
  return arr

属性：

时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
O(n²)	O(n²)	O(n)	O(1)	稳定

使用场景：

少量元素的排序

以上仅供学习~~