写在开头
为什么会有这个系列的文章
因为博主发现自己对排序算法似乎一无所知…所以打算来一发补习
其他
实际上关于对数据的排序一直是一个非常大的问题,我们会发现当数据规模小的时候,多重循环比挨个对并不是什么问题的说,但是在我们的生活当中,我们会发现,数据量讲绝对不止
1000
这道卡,所以我们必须要在中间找到更多更快更好的算法,至于我为什么没有去讲一些奇怪的排序方法(比如猴子排序)是因为它们是一些人们突发奇想的东西,我们虽然不能说它们坏,不过在实际生活中,用处 可能 并不大,所以我们就不会再去提及它们了,有兴趣的话,自己查查吧. 不要去百度!不要去百度!
冒泡排序
时间复杂度:O(n^2)
空间复杂度: 常数级for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i]>a[j]){
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
很明显我们可以看得出来,所谓冒泡排序,就是两个两个之间互相比对,然后大的往上交换(冒泡),于是打了最后,就完成了排序。
所以时间也就意料之中的高2333
插入排序
时空复杂度: 同上 伪代码:
for (int i=1;i<=n;i++){
if (a[i-1]>a[i]){
int temp=a[i];
int j=i;
while(j>0&&a[j-1]>temp){
a[j]=a[j-1];
j--;
}
a[j]=temp;
}
}
选择排序
时空复杂度:仍然同上for(i=1;i<=n;i++){
min=i;
for(j=i+1;j<=n;j++){
if(a[j]<a[min])
min=j;
}
if(min!=i) swap(a[i],a[min]);
}
End
O(n^2)的算法基本上到此为止,后面的排序算法有很多都是从此衍生的,所以说暴力出奇迹是真的2333 ]]>