算法：直接插入排序

以你之姓@ 2023-07-10 14:16 43阅读 0赞

# 基本思想 #

*  插入排序：每次将一个待排序的元素，按照其关键字的带下插入到前面已经排好序的子文件的适当位置，直到全部记录插入完成位置。
 *  直接插入排序：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码比较，将他插入到有序表中的适当位置，使之成为新的有序表。

![在这里插入图片描述][20200303100111286.gif]

# C++实现 #

#include <iostream>
    #include <list>
    #include <vector>
    #include <map>
    
    
    template<typename T>
    std::ostream& print(std::ostream &out,T const &val) {
        
        return (out << val << " ");
    }
    
    template<typename T1,typename T2>
    std::ostream& print(std::ostream &out,std::pair<T1,T2> const &val) {
        
        return (out << "{" << val.first << " " << val.second << "} ");
    }
    
    template<template<typename,typename...> class TT,typename... Args>
    std::ostream& operator<<(std::ostream &out,TT<Args...> const &cont) {
        
        for(auto&& elem : cont) print(out,elem);
        out << "\n";
        return out;
    }
    
    
    void swap(int & i, int &j){
        
        int t = i;
        i = j;
        j = t;
    }
    
    
    
    
    void insertSort(std::vector<int> &vec){
        
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        for(int i = 1; i < vec.size(); i++){
        
            int backup = vec[i];
            int pos = i - 1;
    
            while (pos > -1 && backup < vec[pos]){
        
                vec[pos + 1] = vec[pos];
                pos--;
            }
    
            vec[pos + 1] = backup;
        }
    }
    int main() {
        
        std::vector<int> vec = {
        1,9,2,8,3,7,4,6,5,10, -1};
        insertSort(vec);
        std::cout << vec;
        return 0;
    }

# java实现 #

## 实现1 ##

从小到大

1、定义一个int类型的数组。里面存储着无序的数字

2、从左边开始，假设第一个元素就已经排好序了。

3、取出还没有排好序的数字，从右到左，依次和已经排好序的元素比较，如果待排序的元素比已经排好序的元素小，不需要做什么；如果待排序的元素比已排序的元素小，就将这个待排序的元素插入到这个已排序的元素的前面。

```java
    package array;
    
    public class sort {
        
        public static void main(String []args){
        
            int []arr = {
        199, 11, 23, 56, 55, 49, 88};
            InsertSort(arr);
            printArray(arr);
        }
    
    
        public static int [] InsertSort(int []arr){
        
            if(arr == null || arr.length == 1){
        
                return arr;
            }
    
            for(int i = 1; i < arr.length; i++){
        
                for(int j = i-1; j >= 0; j--){
        
                    if (arr[i] < arr[j]){
        
                        swap(arr, i, j);
                    }
                }
    
            }
    
            return arr;
        }
    
        public static void swap(int []arr, int x, int y){
        
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    
    
    
        public static void printArray(int []arr){
        
            for(int i=0;i<arr.length; i++){
        
                if(i < arr.length - 1){
        
                    System.out.print(arr[i] + ",");
                }else{
        
                    System.out.print(arr[i]);
                }
            }
            System.out.println();
        }
    }

## 实现2【在3种实现中这个比较好】 ##

package com.company;
    
    public class Test_stack {
        
        public static void insertSort(int arrry[]){
        
            // 有序区：元素从小到大排序
            // 有序区逐渐扩大：待比较的元素是无序区的第一个元素
            for (int i = 1; i < arrry.length; i++){
        
    
                 // 如果无序元素 >= 有序元素的最后一个元素，证明无序元素比所有有序元素都要大，就不需要往下
                if (arrry[i] >= arrry[i-1]){
        
                    continue;
                }
    
                // 目的：找到有序区第一个小于value的元素，并且将哪些大于value的元素全部后面移动一位
                //       满足了value < array[pos]才会将 pos的元素往后面移动一位，只有满足了条件才会将pos的元素空出来，
                //                                                             没有满足的时候空出来的位置是pos + 1
                int value = arrry[i];  // 记录要比较的无序元素的值
                int position = i - 1;  //记录无序元素要和哪个有序区的元素比较的位置索引
                while (position > -1 &&value < arrry[position]){
         //0的话还是会比较
                    arrry[position + 1] = arrry[position]; // 元素后移一位
                    position --;
                }
    
                // 跳出循环的可能性：
                    // 不满足 value < array[pos]时， 空出来pos + 1 ， 将value插入到这个位置上
                    //   pos >  -1 ，也就是全部的元素都比较完了， 当前要比较的元素是最小的， 此时value要插入到0也就是pos+1处
                    //  ps： pos = 0 时， 和其他时一样的
                arrry[position + 1] = value;
            }
        }
        public static void main(String[] args) {
        
            int arrry[] = {
        1, 11, 22, 33, 45, 11, 66, 8, 10};
    
            insertSort(arrry);  // 传送的是地址
    
            for (int i:arrry) {
        
                System.out.print(i + "\t");
            }
        }
    }

效率分析：直接从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间上分析，首先外层循环要进行n-1次插入，每次插入最少比较一次\[正序\]，移动0次；最多比较i-1次，移动i次(i=2,3,…n)。因此，直接插入排序的时间复杂度为o(n^2)

## 实现3 ##

// 数组是引用传递
        private static void insertSort(int[] arr){
        
            // 假定第一个元素是有序区
            for (int i = 1; i < arr.length; i++){
         // i是等待排序的元素
                int dindex = i; // 待排序元素的索引
                for (int j = i - 1; j > -1; j--){
        
                    if (arr[dindex] >= arr[j]){
        
                        continue;
                    }
    
                    swap(arr, j, dindex);
                    dindex = j;
                }
            }
        }
    
        private static void swap(int []arr, int i, int j ){
        
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
    
    
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        23,19,81,79,89,83,17,48,55,26,16,1,46,95,10};
            insertSort(arr);
    
            System.out.println(Arrays.toString(arr));
        }

# golang实现 #

package main
    
    import (
    	"fmt"
    )
    
    // 假如我们只插入一个
    func InsertOne(arr [] int)[]int{
        
    	backup := arr[2]; // 备份要比较的元素
    	pos := 2 - 1; //待比较的元素索引
    
    	for pos >= 0 && backup < arr[pos]  {
         //先判断是不是还有坑。 原来坑上的位置大于value
    		arr[pos + 1] = arr[pos]   //将当前坑的元素前移。
    		pos--;
    	}
    
    	// 进入此时： pos = -1 或者 当前位置
    	arr[pos + 1] = backup;
    	return arr;
    }
    
    
    func InsertSort(arr[] int)[]int{
        
    	length := len(arr);
    	if(length <= 1){
        
    		return arr;
    	}else{
        
    		for i := 1; i < length ; i++{
         // 第0个元素不必插入
    			backup := arr[i]; // 备份待排序的元素
    			pos := i - 1; // 看前面的坑。
    
    			if backup >= arr[pos] {
         //如果当前元素比它前面的坑大于等于，就不用往下看了
    				 continue
    			}
    
    			for pos >= 0 && backup < arr[pos]   {
         // pos坑的元素更大，那么就将这个元素前移，并且往下一个坑
    				arr[pos + 1] = arr[pos]
    				pos--;
    			}
    
    
    			arr[pos + 1] = backup;
    		}
    	}
    
    	return arr;
    }
    
    
    func main() {
        
    	arr:=[]int {
        1,9,2,8,3,7,4,6,5,10}
    	fmt.Println(InsertSort(arr))
    	fmt.Println(arr)
    }

直接插入算法的元素移动是顺序的，该方法时稳定的。

使用场景：少量元素大的排序

[手动动画][Link 1]

[知乎总结][Link 2]

[20200303100111286.gif]: https://img-blog.csdnimg.cn/20200303100111286.gif
[Link 1]: http://tools.jb51.net/aideddesign/paixu_ys
[Link 2]: https://zhuanlan.zhihu.com/p/42586566