[数据结构与算法]关于c++中的各种排序

干货来了————

排序算法主要包括：计数排序（桶排序）、插入排序、选择排序、冒泡排序、快速排序等。那这些排序的效率如何呢？

主程序

#include <ctime>
#include <cstdio>
#include <iostream>
#include <memory.h>
#define endl '\n'
using namespace std;

int n, maxn;
int a[20005], b[20005], cnt[2000005];

void quicksort(int [], int, int);
void countsort(int [], int);
void choosesort(int []);
void insertsort(int []);
void pupplesort(int []);
void work();

int main()
{
    work();

    return 0;
}

void quicksort(int a[], int l, int r)
{
    int i = l, j = r, flag = a[(l + r) >> 1], tmp;
    do
    {
        while (a[i] < flag)
            i ++;
        while (a[j] > flag)
            j --;
        if (i <= j)
        {
            swap(a[i], a[j]);
            i ++;
            j --;
        }
    } 
    while (i <= j);
    if (l < j)
        quicksort(a, l, j);
    if (i < r)
        quicksort(a, i, r);

    return ;
}

void countsort(int a[], int maxn) 
{
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i ++)
        cnt[a[i]] ++;
    
    return ;
}

void choosesort(int a[])
{
    for (int i = 1; i < n; i ++)
        for (int j = i + 1; j <= n; j ++)
            if (a[j] < a[i])
                swap(a[i], a[j]);
    
    return ;
}

void insertsort(int a[])
{
    for (int i = 1; i < n; i ++)
    {
        int now = a[i], j;
        for (j = i - 1; j >= 0; j --)
            if (a[j] > now)
                a[j + 1] = a[j];
            else
                break;
        a[j + 1] = now;
    }

    return ;
}

void pupplesort(int a[])
{
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j < n - i; j ++)
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);

    return ;
}

void work()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> b[i];

    double c0 = (double) clock() / CLOCKS_PER_SEC;

    for (int i = 1; i <= n; i ++)
        a[i] = b[i];
    
    quicksort(a, 0, n);

    cout << "Quicksort:" << endl;
    for (int i = 1; i <= n; i ++)
        cout << a[i] << ' ';

    cout << endl;

    double qs = (double) clock() / CLOCKS_PER_SEC;
    
    cout << qs - c0;

    cout << endl << endl;

    maxn = 0;
    for (int i = 1; i <= n; i ++)
        a[i] = b[i], maxn = max(a[i], maxn);

    countsort(a, maxn);

    cout << "Countsort:" << endl;
    for (int i = 1; i <= maxn; i++)
        for (int j = 1; j <= cnt[i]; j++)
            cout << i << ' ';

    cout << endl;

    double cs = (double) clock() / CLOCKS_PER_SEC;

    cout << cs - qs;
    
    cout << endl << endl;

    for (int i = 1; i <= n; i++)
        a[i] = b[i];

    choosesort(a);

    cout << "Choosesort:" << endl;
    for (int i = 1; i <= n; i ++)
        cout << a[i] << ' ';
    
    cout << endl;

    double chs = (double) clock() / CLOCKS_PER_SEC;

    cout << chs - cs;

    cout << endl << endl;

    for (int i = 1; i <= n; i ++)
        a[i] = b[i];

    insertsort(a);

    cout << "Insertsort:" << endl;
    for (int i = 1; i <= n; i ++)
        cout << a[i] << ' ';

    cout << endl;

    double is = (double) clock() / CLOCKS_PER_SEC;

    cout << is - chs;

    cout << endl << endl;

    for (int i = 1; i <= n; i++)
        a[i] = b[i];

    pupplesort(a);

    cout << "Pupplesort:" << endl;
    for (int i = 1; i <= n; i ++)
        cout << a[i] << ' ';

    cout << endl;

    double ps = (double) clock() / CLOCKS_PER_SEC;

    cout << ps - is;

    cout << endl << endl;
    return ;
}

生成数据程序

#include <bits/stdc++.h>
#include <ctime>
using namespace std;

int main ()
{
    // freopen("in.txt", "w" ,stdout);
    srand(time(NULL));
    int n = rand();
    cout << n << endl;
    for (int i = 1; i <= n; i ++)
        cout << rand() << ' ';
    return 0;
}

输入数据

自己生成即可。

输出文件

Quicksort:

0.002

Countsort:

0.004

Choosesort:

1.325

Insertsort:

0.261

Pupplesort:

1.437

可见，quicksort即algorithm里的sort最快。