聚名网是什么_东莞建设企业网站_免费网络营销推广软件_搜索引擎营销经典案例

算法	时间复杂度（最好）	时间复杂度（平均）	时间复杂度（最差）	空间复杂度
插入排序	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;
}