插入排序（Insertion Sort）

谁践踏了优雅 2022-05-26 09:42 164阅读 0赞

一，插入排序算法分析

插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。

然后第一趟 对下标 1 处的元素进行排序，保证数组\[0,1\]上的元素有序；

第二趟 对下标 2 处的元素进行排序，保证数组\[0,2\]上的元素有序；

…..

第N-1趟对下标 N-1 处的元素进行排序，保证数组\[0,N-1\]上的元素有序，也就是整个数组有序了。

它的递归思想就体现在：当对位置 i 处的元素进行排序时，\[0,i-1\]上的元素一定是已经有序的了。

例如：40 80 45 30 20 70  
第一轮：40 `80` 45 30 20 70 —> 40 80 45 30 20 70 i=1  
第二轮：40 80 `45` 30 20 70 —> 40 45 80 30 20 70 i=2  
第三轮：40 80 45 `30` 20 70 —> 30 40 45 80 20 70 i=3  
第四轮：40 80 45 30 `20` 70 —> 20 30 40 45 80 70 i=4  
第五轮：40 80 45 30 20 `70` —> 20 30 40 45 70 80 i=5

例如:  
![这里写图片描述][70]

template<typename T>
    void selectionSort(T arr[], int n)
    {
    
        for (int i = 0; i < n; i++)
        {
    
            int minIndex = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[minIndex])
                    minIndex = j;
    
            swap(arr[i], arr[minIndex]);
        }
    }

优化

template<typename T>
    void insertionSort(T arr[], int n)
    {
        // 寻找元素arr[i]合适的插入位置
        for (int i = 1; i < n; i++)
        {
            T e = arr[i];
            int j;
            for (j = i; j > 0 && arr[j-1] > e; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }

参考博客1：[https://www.cnblogs.com/hapjin/p/5517667.html][https_www.cnblogs.com_hapjin_p_5517667.html]  
参考博客2：[https://blog.csdn.net/llzk\_/article/details/51628574][https_blog.csdn.net_llzk_article_details_51628574]

[70]: /images/20220526/550327d17da7429ea51d06efc554e4d6.png
[https_www.cnblogs.com_hapjin_p_5517667.html]: https://www.cnblogs.com/hapjin/p/5517667.html
[https_blog.csdn.net_llzk_article_details_51628574]: https://blog.csdn.net/llzk_/article/details/51628574