C++排序算法之插入排序 ゝ一纸荒年。 2022-06-12 02:21 145阅读 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
还没有评论,来说两句吧...