排序大集合

排序算法：按关键字顺序按一定方式排列杂乱无章的数据元素的过程。

[En]

Sorting algorithm: the process of arranging disorganized data elements by keyword order in a certain way.

排序方法有多种，如插入排序、希尔排序、冒泡排序、合并排序、选择排序等。这些不同的排序算法的原理也非常不同。

[En]

There are many kinds of sorting methods, such as insert sort, Hill sort, bubble sort, merge sort, select sort. The principles of these different sorting algorithms are also very different.

（小声哔哔：此篇博客中排序算法的定义参考了百度百科qwq……)

Part 1.按算法分类

Part 2.按时间复杂度分类

开始贴代码啦！

（PS:以下所列的排序算法均为从小到大排序）

为了将数据从小到大(升序)排列，在比对和交换的过程中，较小的数字会像气泡一样慢慢漂浮到序列的顶部，因此这种算法被命名为“气泡排序”。

[En]

In order to arrange the data from small to large (ascending order), in the process of comparison and exchange, the smaller numbers will slowly “float” to the top of the sequence like bubbles, so this algorithm is named “bubble sorting”.

冒泡排序 简易版（稳定）

#include
using namespace std;
int a[1000001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i)
      cin>>a[i];
    for(int i=1;i1;i++)//进行n-1轮比较
      for(int j=1;j//每轮比较n-i次
        if(a[j]>a[j+1]) swap(a[j],a[j+1]);//比较大小，交换两数位置
    for(int i=1;i)
      cout<" ";
}

下面的改进版气泡排序，一完成排序就会推导出序列，减少了大量的时间浪费。假设有一个长度为10000的数组，前1000个数据是无序的，后9000个数据是有序的，并且大于前1000个数据。使用上述方法，数据交换次数不到1000次，但剩余的9000次数据不交换，而是在每个周期进行比较。剩下的9000个数据是井然有序的，我们不必对它们进行判断，浪费了不必要的时间。

[En]

The following improved version of bubble sorting will deduce the sequence as soon as the sorting is completed, which has reduced a lot of waste of time. Suppose there is an array of 10000 in length, the first 1000 is unordered, the last 9000 is ordered and larger than the first 1000 data. Using the above method, the number of data exchanges is less than 1000, but the remaining 9000 of the data is not exchanged, but it is compared in each cycle. The remaining 9000 of the data is in order, and we don’t have to judge them, wasting unnecessary time.

冒泡排序 改良版（稳定）

#include
using namespace std;
int a[1000001];
bool f;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i)
      cin>>a[i];
    for(int i=n-1;i>=1;i--)
    {
        f=true;//bool类型变量f判断是否交换
        for(int j=1;j)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                f=false;
            }
        }
        if(f==true) break;
    }
    for(int i=1;i)
      cout<" ";
}

基本思想：把n个待排序的元素看成为一个有序表和一个无序表大数据排序，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

插入排序（稳定）

#include
using namespace std;
int a[1000001];
int main()
{
    int n,temp,i,j,k;
    cin>>n;
    for(i=0;i)
        cin>>a[i];
    for(i=0;i)
    {
        for(j=i-1;j>=0;j--)
            if(a[j]break;//找到比a[i]小的位置就退出，插在它后面
        if(j!=i-1)
        {
            temp=a[i];//将比a[i]大的数向后移
            for(k=i-1;k>j;k--)
                a[k+1]=a[k];
            a[k+1]=temp;
        }
    }
    for(int i=0;i)
      cout<" ";
}

桶排序 (Bucket sort)就是所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再进行个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间O(n)。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。

桶排序（稳定）

#include
using namespace std;
int a[1000001];
int main()
{
    int n,k;
    cin>>n;
    for(int i=1;i)
    {
        cin>>k;
        a[k]++;
    }
    for(int i=0;i1000000;i++)
    {
        while(a[i]>0)
        {
            cout<" ";
            a[i]--;//输出一个整数后，个数减一
        }
    }
 }

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 =1(dt，dt-1…

希尔排序（不稳定）

#include
using namespace std;
int a[1000001];
int main()
{
    int n,k,j;
    cin>>n;
    for(int i=1;i)
        cin>>a[i];
    int gap=n/2;
    while(gap>0)
    {
        for(int i=gap+1;i)
        {
            j=i;
            while(j-gap>0&&a[j]gap])
            {
                swap(a[j],a[j-gap]);
                j=j-gap;
            }
        }
        gap=gap/2;
    }
    for(int i=1;i)
      cout<" ";
}

快速排序是气泡排序的一种改进算法。它也是通过不断比较和移动交换来实现排序，但其实施增加了比较和移动记录之间的距离，将较大的关键字元素直接从前面放到后面，将较小的关键字元素直接从后面放到前面，从而减少了比较和交换的次数。

[En]

Quick sorting is an improved algorithm of bubble sorting. It also achieves sorting by constantly comparing and moving exchanges, but its implementation increases the distance between comparing and moving records, putting larger keyword elements directly from the front to the back, and smaller keyword elements directly from the back to the front, thus reducing the number of comparisons and exchanges.

快速排序（不稳定）

#include
using namespace std;
int a[10000001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i)
      cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i)
     cout<" ";
}

基本思想：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

选择排序（不稳定）

#include
using namespace std;
int a[1000001];
int main()
{
    int n,k;
    cin>>n;
    for(int i=0;i)
        cin>>a[i];
    for(int i=0;i)
    {
        k=i;//选最小的元素a[k]
        for(int j=i+1;j)
            if(a[j]j;
        if(k!=i)//交换a[i]和a[k]，将现在的最小值放在a[i]的位置上
            swap(a[i],a[k]);
    }
    for(int i=0;i)
      cout<" ";
}

结束啦！撒个花！

看在我这么努力的份上，请我喝杯奶茶鸭！

QQ赞赏

微信赞赏

PS：记得给我留下你认为励志与美的句子哦~嘻嘻！

Original:

Author: 浅夏诗吟

Title: 排序大集合

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!