linux c++ 快排，堆排序，插入排序时延对比

heap.h

#ifndef _HEAP_H_
#define _HEAP_H_
#include 

class MaxHeap
{
private:
    void heapAdj(std::vector &num, int i, int len);

public:
    void heapSort(std::vector &nums);
};

class MinHeap
{
private:
    void heapAdj(std::vector &nums, int i, int len);
public:
    void heapSort(std::vector &nums);
};


#endif

heap.cpp

#include "heap.h"
using namespace std;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void MaxHeap::heapAdj(vector& nums, int i, int len)
{
    int j = i * 2 + 1;
    while(j < len)
    {
        if(j + 1 < len && nums[j + 1] > nums[j])
        {
            j++;
        }

        if(nums[i] > nums[j])
        {
            return;
        }
        else
        {
            swap(nums[i], nums[j]);
            i = j;
            j = j * 2 + 1;
        }
    }
}

void MaxHeap::heapSort(vector& nums)
{
    int n = nums.size();
    // build heap
    for(int i = n / 2 - 1;i >= 0; i--)
    {
        heapAdj(nums, i, n);
    }

    for(int i = n - 1; i > 0; i--)
    {
        swap(nums[0], nums[i]);
        heapAdj(nums, 0, i);
    }
}

void MinHeap::heapAdj(vector &nums, int i, int len)
{
    int j = i * 2 + 1;
    while(j < len)
    {
        if(j + 1 < len && nums[j+1] < nums[j])
        {
            j++;
        }

        if(nums[i] < nums[j])
        {
            break;
        }
        else
        {
            swap(nums[i], nums[j]);
            i = j;
            j = i * 2 + 1;
        }
    }
}

void MinHeap::heapSort(vector &nums)
{
    int n = nums.size();

    for(int i = n / 2 - 1; i >= 0; i--)
    {
        heapAdj(nums, i, n);
    }

    for(int i = n - 1; i > 0; i--)
    {
        swap(nums[i], nums[0]);
        heapAdj(nums, 0, i);
    }
}

sort.cpp

#include 
#include 
#include 
#include 
#include 
#include "heap.h"
#include 
using namespace std;

void showData(vector nums)
{
    for(int i=0;i
        printf("%d ", nums[i]);
    }
    printf("n");
}

void genData(vector& nums, int cnt)
{
    for(int i = 0; i < cnt; i++)
    {
        nums.push_back(rand()%cnt);
    }
}

void insertSort(vector& nums)
{
    int n = nums.size();

    for(int i = 0;i < n; i++)
    {
        int p = i;
        for(int j=i;j
            if(nums[j] < nums[p]) p = j;
        }

        if(p != i)
        {
            swap(nums[i], nums[p]);
        }
    }
}

void quickSort(vector& nums, int left, int right)
{
    if(left >= right)
    {
        return;
    }

    int pivot = nums[left];
    int l = left;
    int r = right;

    while(l < r)
    while(l < r)
    {
        while(l < r && nums[r] >= pivot) r--;
        nums[l] = nums[r];

        while(l < r && nums[l] <= pivot) l++;
        nums[r] = nums[l];
    }

    nums[l] = pivot;

    quickSort(nums, left, l - 1);
    quickSort(nums, r + 1, right);
}

uint64_t getTimeNs()
{

    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    uint64_t timestamp = ts.tv_sec * 1000000 + ts.tv_nsec;

    return timestamp;
}

void sortTest(int cnt)
{
    MaxHeap maxheap;
    MinHeap minheap;

    uint64_t start_time = 0;
    uint64_t end_time = 0;

    uint64_t sum1 = 0;
    uint64_t sum2 = 0;
    uint64_t sum3 = 0;

    for(int i=0;i
        vector nums1;
        vector nums2;
        vector nums3;
        genData(nums1, 20);
        nums2 = nums1;
        nums3 = nums1;

        start_time = getTimeNs();
        quickSort(nums1, 0, nums1.size() - 1);
        end_time = getTimeNs();
        sum1 += end_time - start_time;


        start_time = getTimeNs();
        maxheap.heapSort(nums2);
        //minheap.heapSort(nums2);
        end_time = getTimeNs();
        sum2 += end_time - start_time;

        start_time = getTimeNs();
        insertSort(nums3);
        end_time = getTimeNs();
        sum3 += end_time - start_time;
    }

    printf("快排平均时延:%ldn", sum1/cnt);
    printf("堆排序平均时延:%ldn", sum2/cnt);
    printf("插入排序平均时延:%ldn", sum3/cnt);
}


int main()
{
    srand(time(0));

    sortTest(1000);

    return 0;
}

Makefile

CC=g++
SRC=$(wildcard *.cpp)
OBJ=$(patsubst %.cpp, %.o, $(SRC))
TARGET=sort
all:${TARGET}

${TARGET}:${OBJ}
    ${CC} -o $@ $^

%.o:%.cpp
    $(CC) -c $<

clean:
    rm ${OBJ} ${TARGET} -f

测试结果：

结论：
快排 < 堆排序 < 插入排序