数据结构中的排序方式（堆,简单选择,快速,冒泡,希尔,折半插入,直接插入）

直接插入排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn];
int main()
{
    // freopen("10000.txt", "r", stdin);
    for (int i = 1; i <= 10000; i++)
        cin >> a[i];
    clock_t start, finish;
    double  Total_time;
    start = clock();
    for (int i = 2, j; i <= 10000; i++)
    {
        if (a[i] < a[i - 1])
        {
            a[0] = a[i];
            a[i] = a[i - 1];
            for (j = i - 2; a[0] < a[j]; j--)
                a[j + 1] = a[j];
            a[j + 1] = a[0];
        }
    }
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100; i++)
    //     cout << a[i] << endl;
}

折半插入排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn];
int main()
{
    // freopen("1000000.txt", "r", stdin);
    for (int i = 1; i <= 1000000; i++)
        cin >> a[i];
    clock_t start, finish;
    int     low, high, m;
    double  Total_time;
    start = clock();
    for (int i = 2, j; i <= 1000000; i++)
    {
        a[0] = a[i];
        low  = 1, high = i - 1;
        while (low <= high)
        {
            m = (low + high) / 2;
            if (a[0] < a[m])
                high = m - 1;
            else
                low = m + 1;
        }
        for (int j = i - 1; j >= high + 1; j--)
            a[j + 1] = a[j];
        a[high + 1] = a[0];
    }
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100000; i++)
    //     cout << a[i] << endl;
}

希尔排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn], dt[4] = { 1, 3, 5 };
void solve(int dk)
{
    for (int j, i = dk + 1; i <= 1000000; i++)
    {
        if (a[i] < a[i - dk])
        {
            a[0] = a[i];
            for (j = i - dk; j > 0 && a[0] < a[j]; j -= dk)
            {
                a[j + dk] = a[j];
            }
            a[j + dk] = a[0];
        }
    }
}
int main()
{
    // freopen("1000000.txt", "r", stdin);
    for (int i = 1; i <= 1000000; i++)
        cin >> a[i];
    clock_t start, finish;
    int     low, high, m;
    double  Total_time;
    start = clock();
    for (int k = 0; k < 3; k++)
        solve(dt[k]);
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100; i++)
    //     cout << a[i] << endl;
}

冒泡排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn];
int main()
{
    // freopen("1000000.txt", "r", stdin);
    for (int i = 1; i <= 1000000; i++)
        cin >> a[i];
    clock_t start, finish;
    double  Total_time;
    start = clock();
    int     m = 1000000 - 1, flag = 1;
    while ((m > 0) && (flag == 1))
    {
        flag = 0;
        for (int j = 1; j <= m; j++)
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]); flag = 1;
            }
        m--;
    }
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100; i++)
    //     cout << a[i] << endl;
}

快速排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn];
int solve(int low, int high)
{
    a[0] = a[low];
    int mi = a[low];
    while (low < high)
    {
        while (low < high && a[high] >= mi)
            high--;
        a[low] = a[high];
        while (low < high && a[low] <= mi)
            low++;
        a[high] = a[low];
    }
    a[low] = a[0];
    return low;
}
void Qsort(int low, int high)
{
    if (low < high)
    {
        int mid = solve(low, high);
        Qsort(low, mid - 1);
        Qsort(mid + 1, high);
    }
}
int main()
{
    // freopen("1000000.txt", "r", stdin);
    for (int i = 1; i <= 1000000; i++)
        cin >> a[i];
    clock_t start, finish;
    double  Total_time;
    start = clock();
    Qsort(1, 1000000);
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100; i++)
    //     cout << a[i] << endl;
}

简单选择排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn];
int main()
{
    // freopen("100.txt", "r", stdin);
    for (int i = 1; i <= 1000000; i++)
        cin >> a[i];
    clock_t start, finish;
    double  Total_time;
    start = clock();
    for (int i = 1; i < 1000000; i++)
    {
        int k = i;
        for (int j = i + 1; j <= 1000000; j++)
            if (a[j] < a[k])
                k = j;
        if (k != i)
        {
            swap(a[i], a[k]);
        }
    }
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100; i++)
    //     cout << a[i] << endl;
}

堆排序

#include <iostream>
#include <ctime>
using namespace std;
const int maxn = 1e6 + 10;
int       a[maxn];
void solve(int s, int m)
{
    int rc = a[s];
    for (int j = 2 * s; j <= m; j *= 2)
    {
        if (j < m && a[j] < a[j + 1])
            j++;
        if (rc >= a[j])
            break;
        a[s] = a[j]; s = j;
    }
    a[s] = rc;
}
int main()
{
    // freopen("10000.txt", "r", stdin);
    for (int i = 1; i <= 1000000; i++)
        cin >> a[i];
    clock_t start, finish;
    double  Total_time;
    start = clock();
    for (int i = 1000000 / 2; i > 0; i--)
        solve(i, 1000000);
    for (int i = 1000000; i > 1; i--)
    {
        int x = a[1];
        a[1] = a[i];
        a[i] = x;
        solve(1, i - 1);
    }
    finish     = clock();
    Total_time = (double) (finish - start) / CLOCKS_PER_SEC;
    cout << Total_time << endl;
    // for (int i = 1; i <= 100; i++)
    //     cout << a[i] << endl;
}

这是对不同数量级的数据进行时间测试的结果，数据具有偶然性，仅供参考
图片标题