算法 | 时间复杂度(最好) | 时间复杂度(平均) | 时间复杂度(最差) | 空间复杂度 |
---|---|---|---|---|
插入排序 | O(n) | O(n^2) | O(n^2) | 1 |
希尔排序 | O(n) | O(n^1.3) | O(n^2) | 1 |
1.插入排序
玩牌时,每得到一张,就要把它插入到之前的牌中,插入排序也是如此,每次都有一个有序的区间,每次都要选取无序区间的第一个元素,把他插入到合适的位置,这时,有序区间的长度+1,直到和序列长度相等为止
代码:
#include<bits/stdc++.h>
using namespace std;
int main() {int n, a[10000];cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {int s = i;while (a[s] < a[s - 1] && (s > 0)) {swap(a[s], a[s - 1]);s --;}}for (int i = 0; i < n; i++) {cout << a[i] << ' ';}return 0;
}
复杂度分析:平均情况:每个元素都要进行插入,要进行n次插入,时间复杂度为O(n*n)
最好情况:近乎有序序列,插入的时间可以忽略不计,时间复杂度:O(n)
2.希尔排序
由他的发明者希尔命名,它会进行多次预排序,使其整体接近有序,每次都是插入排序里的1替换成gap,而gap先从n/2开始,以一定的规律递减,直到一。效率跟增量的序列有关。
时间复杂度:最好,最坏和插入排序一样。
为什么要这么做
因为gap大时,每一组数据量少,效率高,gap小时,整体接近有序,效率也高。所以整体效率比插入排序高!
#include<bits/stdc++.h>
using namespace std;
int main(){int n,a[10000],gap;cin>>n;gap=n;for(int i=0;i<n;i++){cin>>a[i];}while(gap>=1){gap*=0.6;//找不到其它序列了qwq。。。for(int i=0;i<=n-gap;i++){int s=i;while(a[s]<a[s-gap]&&(s-gap>=0)){a[s]^=a[s-gap];a[s-gap]^=a[s];a[s]^=a[s-gap];s-=gap;}}}for(int i=0;i<n;i++){cout<<a[i]<<' ';}return 0;
}