#
18610508486@163.com


## 

**Insertion Sort**[](https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95)****in-placeO(1)

##

****in-place

1. 
2. 
3. 
4. 3
5. 
6. 2~5

## pythongolang

###python 

    #coding:utf-8
        """
        python
        https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.md
        python
        https://github.com/pythonpeixun/article/blob/master/index.md
        python
        https://github.com/pythonpeixun/article/blob/master/python_shiping.md
        
        qq:1465376564
        """

        def insert_sort(lst):
            length = len(lst)
            for i in range(1, length):
                tmp = lst[i]
                for j in range(i-1, -1, -1):
                    if lst[j] > tmp:
                        lst[j+1] = lst[j]
                    else:
                        lst[j+1] = tmp
                        break
                if lst[0] > tmp:
                    lst[0] = tmp

        if __name__ == '__main__':
            lst = [8, 2, 4, 1, 9, 20, 15, 6, 0]
            insert_sort(lst)
            print(lst)


###golang    

    package main

        import (
        	"fmt"
        )

        func InsertSort(lst []int) {

        	length := len(lst)
        	for i := 1; i < length; i++ {
        		tmp := lst[i]
        		for j := i - 1; j >= 0; j-- {
        			if lst[j] > tmp {
        				lst[j+1] = lst[j]
        			} else {
        				lst[j+1] = tmp
        				break
        			}

        		}
        		// golang jfor
        		// 
        		if lst[0] > tmp {
        			lst[0] = tmp
        		}

        	}
        }
        func main() {

        	lst := []int{3, 8, 2, 9, 7, 12, 33, 6, 97, 48, 23}
        	InsertSort(lst)
        	fmt.Println(lst)
        }

##c    

      void insertion_sort(int arr[], int len) {
      	int i, j;
      	int temp;
      	for (i = 1; i < len; i++) {
      		temp = arr[i]; //temp
      		for (j = i - 1; j >= 0 && arr[j] > temp; j--) //j-1array[-1]
      			arr[j + 1] = arr[j];
      		arr[j+1] = temp; //
      	}
      }

##python 2    

    def insertion_sort(n):
        if len(n) == 1:
            return n
        b = insertion_sort(n[1:])
        m = len(b)
        for i in range(m):
            if n[0] = 0 and temp < lst[j]:
                lst[j + 1] = lst[j]
                j -= 1
            lst[j + 1] = temp
##

n*****(n-1)**n(n-1)/2******(n-1)*******O(n2)********** STLsortstdlibqsort8

[python](https://github.com/pythonpeixun/article/blob/master/python_shiping.md)

[python](https://github.com/pythonpeixun/article/blob/master/index.md)