排序算法运行时间比较

在Fedora 31上安装google-benchmark,

dnf install google-benchmark-devel

代码：

#pragma GCC optimize("-O3")

void insertionSort(int * arr, int n)
{
    for (int i = 1; i < n; i++)
    {
        int value = arr[i];
        int j = i;

        while (j > 0 && arr[j - 1] > value)
        {
            arr[j] = arr[j - 1];
            j--;
        }

        arr[j] = value;
    }
}

void swap(int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void selectionSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;

        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min])
                min = j;    
        }

        swap(arr, min, i);
    }
}

void bubbleSort(int arr[], int n)
{
     for (int k = 0; k < n - 1; k++)
     {
          for (int i = 0; i < n - 1 - k; i++) {
               if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
               }
          }
     }
}

void Merge(int arr[], int aux[], int low, int mid, int high)
{
    int k = low, i = low, j = mid + 1;

    while (i <= mid && j <= high)
    {
        if (arr[i] < arr[j])
            aux[k++] = arr[i++];
        else
            aux[k++] = arr[j++];
    }

    while (i <= mid)
        aux[k++] = arr[i++];

    for (int i = low; i <= high; i++)
        arr[i] = aux[i];
}

void mergeSort(int arr[], int aux[], int low, int high)
{
    if (high == low)    // if run size == 1
        return;

    int mid = (low + ((high - low) >> 1));

    mergeSort(arr, aux, low, mid);      // split / merge left  half
    mergeSort(arr, aux, mid + 1, high); // split / merge right half

    Merge(arr, aux, low, mid, high);    // merge the two half runs
}

#include <iostream>
#include <algorithm>
using namespace std;

// Partition using Lomuto partition scheme
int Partition(int a[], int start, int end)
{
    // Pick rightmost element as pivot from the array
    int pivot = a[end];

    // elements less than pivot will be pushed to the left of pIndex
    // elements more than pivot will be pushed to the right of pIndex
    // equal elements can go either way
    int pIndex = start;

    // each time we finds an element less than or equal to pivot, pIndex
    // is incremented and that element would be placed before the pivot.
    for (int i = start; i < end; i++)
    {
        if (a[i] <= pivot)
        {
            swap(a[i], a[pIndex]);
            pIndex++;
        }
    }
    // swap pIndex with Pivot
    swap (a[pIndex], a[end]);

    // return pIndex (index of pivot element)
    return pIndex;
}

// Quicksort routine
void quickSort(int a[] ,int start, int end)
{
    // base condition
    if (start >= end)
        return;

    // rearrange the elements across pivot
    int pivot = Partition(a, start, end);

    // recur on sub-array containing elements that are less than pivot
    quickSort(a, start, pivot - 1);

    // recur on sub-array containing elements that are more than pivot
    quickSort(a, pivot + 1, end);
}



#include <benchmark/benchmark.h>

void bm_insertionSort(benchmark::State& state)
{
    int arr[] = { 1, 3, 3, 9, 6, 5, 7, 7, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    for (auto _ : state) {
        insertionSort(arr, n);
    }
}
BENCHMARK(bm_insertionSort);

void bm_selectionSort(benchmark::State& state)
{
    int arr[] = { 1, 3, 3, 9, 6, 5, 7, 7, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    for (auto _ : state) {
        selectionSort(arr, n);
    }
}
BENCHMARK(bm_selectionSort);

void bm_bubbleSort(benchmark::State& state)
{
    int arr[] = { 1, 3, 3, 9, 6, 5, 7, 7, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    for (auto _ : state) {
        bubbleSort(arr, n);
    }
}
BENCHMARK(bm_bubbleSort);

void bm_mergeSort(benchmark::State& state)
{
    int arr[] = { 1, 3, 3, 9, 6, 5, 7, 7, 2, 6 };
    int aux[] = { 1, 3, 3, 9, 6, 5, 7, 7, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    for (auto _ : state) {
        mergeSort(arr, aux, 0, n-1);
    }
}
BENCHMARK(bm_mergeSort);

void bm_quickSort(benchmark::State& state)
{
    int arr[] = { 1, 3, 3, 9, 6, 5, 7, 7, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    for (auto _ : state) {
        quickSort(arr, 0, n-1);
    }
}
BENCHMARK(bm_quickSort);

BENCHMARK_MAIN();

$ cat a.sh
#!/usr/bin/bash
g++ a.cpp -lbenchmark
./a.out

$ ./a.sh
2019-09-26 03:11:24
Running ./a.out
Run on (2 X 2496 MHz CPU s)
CPU Caches:
  L1 Data 32K (x2)
  L1 Instruction 32K (x2)
  L2 Unified 256K (x2)
  L3 Unified 3072K (x2)
Load Average: 0.24, 0.15, 0.07
-----------------------------------------------------------
Benchmark                 Time             CPU   Iterations
-----------------------------------------------------------
bm_insertionSort       10.5 ns         10.4 ns     65398135
bm_selectionSort       56.0 ns         55.3 ns     11485787
bm_bubbleSort          43.0 ns         42.4 ns     17086558
bm_mergeSort            111 ns          110 ns      6547776
bm_quickSort            525 ns          506 ns      1000000

参考

https://medium.com/@codingfreak/top-algorithms-data-structures-concepts-every-computer-science-student-should-know-e0549c67b4ac