几种简单排序的时间复杂度比较

#include <iostream>
#include <fstream>
#include <windows.h>
#include <math.h>
using namespace std;
int arr[40000];
ofstream out("out.txt");
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
/*交换次数即为逆序对*/
void InitArr(int arr[], int N)
{
    ifstream in("H:/vscode/in.txt");
    for (int i = 0; i < N; i++)
        in >> arr[i];
}
void output(int arr[], int N)
{
    for (int i = 0; i < N; i++)
        out << arr[i] << " ";
    out << endl;
}
void Bubble_Sort(int arr[], int N)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N - i - 1; j++)
        {
            if (arr[j + 1] < arr[j])
            {
                swap(arr[j + 1], arr[j]);
            }
        }
    }
}
void Insert_Sort(int arr[], int N)
{
    for (int i = 1; i < N; i++)
    {
        int j;
        int temp = arr[i];
        for (j = i; j > 0 && temp < arr[j - 1]; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}
void Shell_Sort(int arr[], int N)
{
    for (int D = N / 2; D > 0; D /= 2)
    {
        for (int i = 1; i < N; i += D)
        {
            int j;
            int temp = arr[i];
            for (j = i; j > 0 && arr[j - 1] > temp; j--)
                arr[j] = arr[j - 1];
            arr[j] = temp;
        }
    }
}
void ShellSort_Sedgewick(int arr[], int N)
{
    int Si, D, P, i;
    int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

    for (Si = 0; Sedgewick[Si] >= N; Si++)
        ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

    for (D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si])
    {
        for (P = D; P < N; P++)
        { /* 插入排序*/
            int Temp = arr[P];
            for (i = P; i >= D && arr[i - D] > Temp; i -= D)
                arr[i] = arr[i - D];
            arr[i] = Temp;
        }
    }
}
void CostTime(int arr[], int N, void (*Pfun)(int[], int), string name)
{
    double time = 0;
    LARGE_INTEGER nFreq;
    LARGE_INTEGER nBeginTime;
    LARGE_INTEGER nEndTime;
    QueryPerformanceFrequency(&nFreq);
    QueryPerformanceCounter(&nBeginTime);
    Pfun(arr, N);
    QueryPerformanceCounter(&nEndTime);
    time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;
    out << name << "执行时间：" << time * 1000 << "ms" << endl;
    output(arr, N);
    out << endl;
}
int main()
{
    int N = 20000;
    InitArr(arr, N);
    CostTime(arr, N, Bubble_Sort, "冒泡排序");
    InitArr(arr, N);
    CostTime(arr, N, Insert_Sort, "插入排序");
    InitArr(arr, N);
    CostTime(arr, N, Shell_Sort, "希尔排序");
    InitArr(arr, N);
    CostTime(arr, N, ShellSort_Sedgewick, "Sedgewick序列希尔排序");
}

#include <iostream>
#include <fstream>
#include <time.h>
#define N 100000        //生成N个随机数
using namespace std;
ofstream out("in.txt");    //数组可以直接从文件读入
int array[N];
int main()
{
    srand(time(NULL));
    for (int i = 0; i < N; i++)
        array[i] = rand();
    for (int i = 0; i < N; i++)
        out << array[i] << " " ;
}