冒泡排序

方法

第一次将每一个元素和它的后一个元素比较大小，如果不满足顺序则交换，这样即可确定最后一个数的位置。然后再从头开始，可以确定倒数第二个数的位置。循环n次后即可完成排序。因为每一轮排完序后都会确定一个，即“冒”出来一个，故被称作冒泡排序。

时间效率：O($n^{2}$)

代码

以 洛谷 P1116 车厢重组 为例

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,d,e,ans;
int f[10005];
void change(int &a,int &b)
{
    int c;
    c=a;
    a=b;
    b=c;
}
int main()
{
    cin>>n;
    for (a=1;a<=n;a++)
    cin>>f[a];
    for (a=1;a<=n;a++)
      for (b=1;b<=n-a;b++)//因为每次多确定一位，固少循环一次
      if (f[b]>f[b+1])
      {
          change(f[b],f[b+1]);
          ans++;
      }
    cout<<ans;
    return 0;
}

桶排序

桶排序的原理非常简单，即将需排序的元素作为数组下标，直接输出就行了。

时间效率：O(n) 但是需要很多额外空间

归并排序

方法

运用递归将原数据不断二分，然后在回溯过程中使用归并算法将其一步步合并，最后合成一个有序数列。



时间效率：最好：O(log n) 最坏：O(n*log n)

代码

以 洛谷 P1177 【模板】快速排序 为例

#include<bits/stdc++.h>
using namespace std;
int n,m,p,i,j,k;
queue <int> q;
int f[100005];
void merge_sort(int a,int b)//a是起点，b是终点
{
    int s;
    if (a==b) return;
    s=(a+b)/2;
    merge_sort(a,s);
    merge_sort(s+1,b);//递归调用
    i=a;
    j=s+1;
    while (i<=s&&j<=b)
    {
        if (f[i]>f[j]) 
        {
            q.push(f[j]);
            j++;
        }
        else
        {
            q.push(f[i]);
            i++;
        }
    }
    if (i>s) 
    for (int e=j;e<=b;e++) q.push(f[e]);
    if (j>b)
    for (int e=i;e<=s;e++) q.push(f[e]);
    k=a-1;
    while (!q.empty())
    {
        k++;
        f[k]=q.front();
        q.pop();
    }//归并算法
}
int main()
{
    cin>>n;
    for (int a=1;a<=n;a++)
    cin>>f[a];
    merge_sort(1,n);
    for (int a=1;a<=n;a++)
    cout<<f[a]<<" ";
    return 0;
}

快速排序

方法

1. 设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2. 以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3. 从j开始向前搜索，即由后开始向前搜索(j—)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5. 重复第3、4步，直到i=j，这样以后第i位上的数的前面比这个数小，后面比这个数大，即这个数位置已经确定；
6. 将i前面和i后面的部分递归调用再次排序，直到排完。

代码

sort(A,A+N,com)//_huaji

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/sort.html