关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年4月1日
排序算法(1) — O(n^2)类型 — 冒泡排序/插入排序/选择排序

写在开头

为什么会有这个系列的文章


因为博主发现自己对排序算法似乎一无所知…所以打算来一发补习

其他


实际上关于对数据的排序一直是一个非常大的问题,我们会发现当数据规模小的时候,多重循环比挨个对并不是什么问题的说,但是在我们的生活当中,我们会发现,数据量讲绝对不止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;
    }
}

为什么我感觉比上面的那种还暴力

暴力出奇迹233 这种办法的本质就是直接插入,找到比自己大的很比自己小的,然后往中间插队(插入),然后出来就算排序好了 巧了入学时队伍就是这么排出来的的

选择排序

时空复杂度:仍然同上

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


textsms