上一节课呢, 我们学习了冒泡排序, 今天我们就来学学插入排序.
先看一个图
很显然, 我们要选出一个数, 并找到他的位置, 就像图中的一样.
有过一定生活经验的人会发现, 这句就是打牌时的理牌嘛!
我们首先要用 O(n) 的时间来枚举每一个点, 再用 O(n) 的时间查它之前在序列中的应有位置, 所以, 总复杂度是 O(n^2).
我们来看看代码:
- #include<iostream>
- using namespace std;
- int n,a[10001],t,j,k;// 循环之外要用的 j,k
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- cin>>a[i];
- for(int i=1;i<=n;i++)
- {
- for(j=i-1;j>=0;j--)
- if(a[j]<a[i])// 找到比 a[i] 小的位置就退出, 插入其后
- break;
- if(j!=i-1)
- {
- t=a[i];
- for(k=i-1;k>j;k--)
- a[k+1]=a[k];// 位置前移一个
- a[k+1]=t;
- }
- }
- for(int i=1;i<=n;i++)
- cout<<a[i]<<" ";
- cout<<endl;
- return 0;
- }
这个代码看似和 bubblesort 冒泡排序很像, 但是它的不同在于使用了全局变量 j,k 来储存 a[i] 应有的位置和现在所属的位置.
有时候这个代码很难理解, 但是理清思路, 最后也是很好理解的.
代码的关键在于:
- for(j=i-1;j>=0;j--)
- if(a[j]<a[i])
- break;
- if(j!=i-1)
- {
- t=a[i];
- for(k=i-1;k>j;k--)
- a[k+1]=a[k];
- a[k+1]=t;
- }
其实, 说句实话, 插入排序的运用真的不广泛. 只要懂得, 不必太深究.
今天的课程就到这里, 明天我们要讲选择排序, 我们明天见!
来源: https://yq.aliyun.com/articles/674910