几种排序方法总结

@Llf  February 7, 2018

冒泡排序

方法

第一次将每一个元素和它的后一个元素比较大小,如果不满足顺序则交换,这样即可确定最后一个数的位置。然后再从头开始,可以确定倒数第二个数的位置。循环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

添加新评论