排序算法(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 ]]>