插入排序详解

今天药忘吃喽~ 2022-07-18 01:50 56阅读 0赞

**基本概念：**

通常人们整理扑克牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余元素在插入之前都向右移动一位。这种算法叫插入排序（**insert sort**）。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：  
1.从第一个元素开始，该元素可以认为已经被排序  
2.取出下一个元素，在已经排序的元素序列中**从后向前扫描**  
3.如果该元素（已排序）大于新元素，将该元素移到下一位置  
4.重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置  
5.将新元素插入到该位置后  
6.重复步骤 2~5

插入排序的时间复杂度为**O(n²)**，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况，不能简单的用来计算精确值。

**过程如图：**

![20160904230557056][]

**简单例子：**

#include <stdio.h>
    
    void insert_sort(int arr[], int size)
    {
        if (arr == NULL)
            return ;
    
        int i, j, temp;
        for (i = 1; i < size; ++i) {
            /* 将a[i]插入到a[i-1]、a[i-2]、a[i-3]...中 */
            for (j = i; j > 0 && (arr[j] < arr[j - 1]); --j) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
    
            /* 每轮内循环后输出数组的现状 */
            int k;
            printf("the %d for(): ", i);
            for (k = 0; k < size; ++k) {
                printf("%d ", arr[k]);
            }
            printf("\n");
    
        }
    }
    
    
    int main()
    {
        int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
        int size = sizeof(arr) / sizeof(int);
    
        //sort
        insert_sort(arr, size);
    
        //print
        int i = 0;
        for (i; i < size; ++i) {
            printf("%d\n", arr[i]);
        }
    
        return 0;
    }

**编译运行：**

![SouthEast][]

原文出自：[http://blog.csdn.net/daiyudong2020/article/details/52435348][http_blog.csdn.net_daiyudong2020_article_details_52435348]

End;

[20160904230557056]: /images/20220717/95554aed3d3e4b0f93817816bfbb8231.png
[SouthEast]: /images/20220717/1078c99ee53c454db8a9901250c30744.png
[http_blog.csdn.net_daiyudong2020_article_details_52435348]: http://blog.csdn.net/daiyudong2020/article/details/52435348