插入排序 Insertion Sort

原理

插入排序（Insertion Sort）是一种简单直观的排序算法，灵感来自整理扑克牌的过程。在排序时，每次从未排序部分中取出一个元素，将它插入到已排序部分的适当位置，直到所有元素都被插入。其特点是操作相对简单，但效率较低，适用于小规模数据的排序。

其具体步骤如下：

从第二个元素开始，将当前元素与它前面已排序的元素进行比较。
如果当前元素比前面的某个元素小，则将其插入到该元素前面。
重复上述步骤，直到所有元素都排序完成。

示例

有一组无序数组：

6	2	4	1	9	0	3

此时将6作为有序数组，用2向前比对。此时2比6小，2插入6前面。

此时数组为：

		4	1	9	0	3

此时将2 6作为有序数组，用4从头比对。此时4比2大且4比6小，4插入2后6前。

此时数组为：

			1	9	0	3

此时将2 4 6作为有序数组，用1从头比对。此时1比2小，1插入2前面。

此时数组为：

				9	0	3

此时将1 2 4 6作为有序数组，用9从头比对。此时9比最大值6大，9插入6后面。

此时数组为：

					0	3

此时将1 2 4 6 9作为有序数组，用0从头比对。此时0比1小，0插入1前面。

此时数组为：

						3

此时将0 1 2 4 6 9作为有序数组，用3从头比对。此时3比2大且3比4小，3插入2后4前。

此时数组为：

排序完成。

实现

C++

cpp

#include <iostream>
#include <vector>
using namespace std;

std::vector<int> InsertionSort(std::vector<int> besortedArray);
std::vector<int> myArray = { 6, 2, 4, 1, 9, 0, 3, 10, 15 };

int main()
{
    std::vector<int> testArray = InsertionSort(myArray);
    //输出：0 1 2 3 4 6 9 10 15
    for (int i = 0; i < testArray.size(); i++) {
        cout << testArray[i] << " ";
    }
    return 0;
}

//插入排序
std::vector<int> InsertionSort(std::vector<int> besortedArray)
{
    int length = besortedArray.size();
    for(int i = 1; i < length; i++) 
    {
        for (int j = 0; j < i; j++)
        {
            bool select = (j == 0 && besortedArray[i] <= besortedArray[j]) || (j > 0 && besortedArray[i] <= besortedArray[j] && besortedArray[i] > besortedArray[j-1]);
            if (select) {
                int t = besortedArray[i];
                for (int k = i; k > j; k--)
                {
                    besortedArray[k] = besortedArray[k - 1];
                }
                besortedArray[j] = t;
                break;
            }
        }
    }
    return besortedArray;
}

可视化

数组长度

动画间隔

数组：

[]

插入排序 Insertion Sort ​

原理 ​

示例 ​

实现 ​

C++ ​

可视化 ​

插入排序 Insertion Sort

原理

示例

实现

C++

可视化