几大常用的排序算法一

1.桶排序

桶排序很简单，假如现在有10个数，需要对它们进行排序，首先我们就创建一个大小为10的数组来代表10个桶，然后将这10个数遍历一遍，这个数是几就放入第几个桶中，最后将所有桶遍历一遍，将桶中的数输出即可

下面来一个实例，第一行输入要排序的数的个数，第二行输入具体的数值，最后输出排序过后的数

具体代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include<bits/stdc++.h>
using namespace std;
int book[1001];
int main(){
    int t,n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t;
        book[t]++;
    }
    for(int i=0;i<1000;i++){
      for(int j=1;j<=book[i];j++){
        cout<<i<<" ";
      }
    }
}

桶排序有它的优点：非常快，但是他也有很明显的缺点，假如现在有5个人的名字和分数，要求按照从低到高输出它们的分数和名字，这时候我们使用上面的桶排序就只能对分数进行排序无法对人进行排序，桶排序除了这个问题外，还有最大的问题是非常浪费空间，如果我们要排序的数个数非常少，但是数值的范围特别大，这时候就会造成空间的浪费

2.冒泡排序

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来

首先我们先用冒泡排序对上面桶排序中的实例进行实现

具体代码如下： /#include<bits/stdc++.h> using namespace std; int a[100]; int main(){ int n; int t; cin»n; for(int i=1;i<=n;i++){ cin»a[i]; } for(int i=1;i<=n-1;i++){ for(int j=1;j<=n-i;j++){ if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(int i=1;i<=n;i++){ cout«a[i]«" “; } }

在冒泡排序中，只需要对代码稍加修改，就可以解决上边桶排序中不能对人名进行排序的问题了

具体代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#include<bits/stdc++.h>
using namespace std;
int a[100];
int main(){
    int n;
    int t;
    cin>>n;
    for(int i=1;i<=n;i++){
       cin>>a[i];
    }
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=n-i;j++){
           if(a[j]>a[j+1]){
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
           }
        }
    }
   for(int i=1;i<=n;i++){
    cout<<a[i]<<" ";
   }
}

冒泡排序的核心部分就是双重嵌套循环，所以时间复杂度是O(N2)；这是一个非常高的复杂度

3.快速排序

冒泡排序才算是真正的排序算法，第一部分讲的桶排序不能算是真正的排序算法，因为那不是真正的桶排序，真正的桶排序比这要复杂的多，冒泡排序解决了桶排序浪费空间的问题，但是在执行效率上却不行

所以就有了快速排序，即不浪费空间有可以提高效率

快速排序就是基于二分法的

具体代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include<bits/stdc++.h>
using namespace std;
struct student
{
    char name[21];
    int score;
};
int main(){
  struct student a[100],t;
  int i,j,n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].name>>a[i].score;
  }
  for(int i=1;i<=n-1;i++){
    for(int j=1;j<=n-i;j++){
        if(a[j].score>a[j+1].score){
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
        }
    }
  }
  for(int i=1;i<=n;i++){
    cout<<a[i].name<<" "<<a[i].score<<endl;
  }
}

讲解一下代码的实现思路：

假设这里有一组要进行快速排序的数：6 1 2 7 9 3 4 5 10 8

以第一个数6为基准数，然后从左右边往左出发，直到找到一个比基准数小的数停下来，然后再从左往右出发，直到找到一个比6大的数停下来，如果此时从右往左和从左往右还没有相遇的话，就交换两个位置的数，直到相遇位置，这时候相遇的位置就是基准数需要交换的位置，然后对归位后的6的左边和右边的数递归调用即可

快速排序之所以快，是因为相比于冒泡排序，每次交换都是跳跃式的，每次排序的时候设置一个基准点，将小于等于基准点的都放到基准点的左边，大于等于基准点的都放到基准点的右边，这样总的交换和比较次数就变少了，速度自然就提高了

快速排序的最差情况下的时间复杂度是和和冒泡排序一样，O(N2)，平均时间复杂度为O(NlogN)，

最后修改于 2021-03-08

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。