C++排序算法之插入排序

ゝ一纸荒年。 2022-06-12 02:21 191阅读 0赞

**直接插入排序**

思路：将数组分成两部分，前一部分是已经有序的序列，后一部分是待排序列。每一趟将待排序列的第一个元素作为关键字，根据其关键字的大小插入到已经排好序的那部分序列的适当位置，知道插入完成，整个序列有序为止。

例如：3 6 4 2 1 8 5 7

（1）开始只看到3，一个数当然是有序的

3 6 4 2 1 8 5 7

（2）插入6。3<6，不需要移动，6就应该在3之后，这趟排序的结果为

3 6 4 2 1 8 5 7

（3）插入4。4<6，所以6向后移动一个位置；4>3，所以不需要移动，4应该插入到3和6之间，这趟排序结果为

3 4 6 2 1 8 5 7

（4）插入2。2<6，所以6向后移动一个位置；2<4，4向后移动一个位置；2<3,3向后移动一个位置。最后发现2应该插入到最前面，结果为

2 3 4 6 1 8 5 7

（5）插入1。1<6，所以6向后移动一个位置.........；这样逐个向前比较，发现1应该插入最前边，结果为

1 2 3 4 6 8 5 7

（6）插入8。结果为

1 2 3 4 6 8 5 7

（7）插入5。结果为

1 2 3 4 5 6 8 7

（8）最后插入7。结果为

1 2 3 4 5 6 7 8

插入完成。

代码实现如下：

#include <iostream>
    #include <vector>
    using namespace std;
    
    //插入排序法，默认按升序排列，时间复杂度为 最差为O(n*n)，最好为O(n)，平均时间复杂度为O(n*n)；空间复杂度为O(1)
    //待排数据存放在R[]中，默认为整型，个数为n
    void InsertSort(vector<int> &R)
    {
    	int i, j;
    	int temp;
    	for ( i = 1; i < R.size(); i++)
    	{
    		temp = R[i];                                   //将待插入的元素暂存在temp中
    		j = i-1;
    		//下面的循环完成了从待排元素之前的元素开始扫描，如果大于待排元素，则后移一位
    		while (j >= 0 && R[j] > temp)
    		{
    			R[j + 1] = R[j];
    			--j;
    		}
    		R[j + 1] = temp;                          //找到插入位置，将temp中暂存的元素插入
    	}
    	//return R;
    }
    
    void main()
    {
    	vector<int> R = { 3,6,4,2,1,8,5,7 };
    	InsertSort(R);
    	for (auto x : R)
    		cout << x << " ";
    	cout << endl;
    }

输出结果为

![Center][]

**复杂度分析：**

**（1）时间复杂度**

*  **考虑最坏情况，**即整个序列逆序，则内层循环中temp<R\[j\]这个条件始终成立。此时对于每次外层循环，内层循环的执行次数达到最大值，为i次（如当外层循环i等于5时，内层循环j从0-4，执行5次）。i的取值范围为1-n-1,由此可得基本操作执行次数为(1+n-1)(n-1)/2=n(n-1)/2.因此时间复杂度为**O(n^2)**.
 *  **考虑最好情况**，即整个序列有序，则对于内层循环temp<R\[j\]这个条件始终不成立，此时内层循环始终不执行，双层循环变成了单层循环，时间复杂度为**O(n)**。
 *  综合以上两种情况，**平均时间复杂度为O(n^2)**

**（2）空间复杂度**

额外辅助空间只有一个temp ,因此空间复杂度为 **O(1)**。

[Center]: /images/20220612/7a8ebe37608e4737a22755a346406fe7.png