c++ - 内省(introspection)排序有问题

Question

我正在尝试使用不同的算法对数组进行排序。我使用的每个算法似乎都可以正常工作，但是我的 IntroSort 的行为很奇怪。它总是比 QuickSort 慢，对于大量元素，例如百万，它需要几分钟，而 QuickSort 大约需要。 1.2 秒。

我尝试为内省(introspection)、堆和插入排序重写代码几次，结果相同。这种行为的原因是什么？我的代码有问题吗？

我正在使用的函数(来自文件算法.h)

#pragma once

template <typename T>
void display_array(T* arr, int n) {     // displays full array in one line
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

template <typename T>
void swap_values(T* x, T* y) {          // swaps two values
    T tmp = *x;
    *x = *y;
    *y = tmp;
}

/* * * * Quick Sort * * * */
template <typename T>
int quickS_part(T* arr, int left, int right) {
    int position = left;
    T pivot = arr[right];

    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap_values(&arr[i], &arr[position]);
            position++;
        }
    }

    swap_values(&arr[position], &arr[right]);

    return position;
}

template <typename T>
void quick_sort(T* arr, int left, int right) {
    if (left < right) {
        int pivot = quickS_part(arr, left, right);

        quick_sort(arr, left, pivot - 1);
        quick_sort(arr, pivot + 1, right);
    }
}

/* * * * Heap Sort * * * */
template <typename T>
void heapify(T* arr, int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < size && arr[left] > arr[largest])
        largest = left;
    if (right < size && arr[right] > arr[largest])
        largest = right;

    if (largest != root) {
        swap_values(&arr[root], &arr[largest]);
        heapify(arr, size, largest);
    }
}

template <typename T>
void heap_sort(T* arr, int size) {
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(arr, size, i);

    for (int i = size - 1; i >= 0; i--) {
        swap_values(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

/* * * * Insertion Sort * * * */
template <typename T>
void insertion_sort(T* arr, int left, int size) {
    for (int i = 1; i < size; i++) {
        T k = arr[i];
        int j = i - 1;
        while (k < arr[j] && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

/* * * * Introspective Sort * * * */
template <typename T>
void introS(T* arr, int left, int right, int maxdepth) {
    if ((right - left) < 16)
        insertion_sort(arr, left, right + 1);
    else if (maxdepth == 0)
        heap_sort(arr, right + 1);
    else {
        int pivot = quickS_part(arr, left, right);

        introS(arr, left, pivot - 1, maxdepth - 1);
        introS(arr, pivot + 1, right, maxdepth - 1);
    }
}

template <typename T>
void intro_sort(T* arr, int left, int right) {
    int md = 2 * floor(log(right + 1));
    introS(arr, left, right, md);
}

main.cpp:

#include <iostream>
#include <ctime>
#include <chrono>
#include <cmath>
#include "algorithms.h"

int main()
{
    //srand(time(NULL));

    const int size = 1000000;
    int *test1;
    test1 = new int[size];

    for (int i = 0; i < size; i++)
        test1[i] =  rand() % 1000000;

    auto start = std::chrono::high_resolution_clock::now();

    intro_sort(test1, 0, size - 1);

    auto end = std::chrono::high_resolution_clock::now();
    double time = std::chrono::duration<double, std::milli>(end - start).count();

    std::cout << "Sorting took " << time << " milliseconds." << std::endl;

    delete[] test1;
    return 0;
}

Answer 1

事实证明，堆排序和插入排序没有正确实现。我认为发生的情况是，当它们被调用时，它们会尝试对整个数组而不是其中的一部分进行排序。

这是对我有用的正确版本:

插入排序:

template <typename T>
void insertion_sort(T* arr, int left, int size) {
    for (int i = left; i < size; i++) {
        T k = arr[i];
        int j = i - 1;
        while (k < arr[j] && j >= left) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

堆排序:

template <typename T>
void heap_sort(T* arr, int start, int size) {
    for (int i = size / 2 - 1; i >= start; i--)
        heapify(arr, size, i);                 // there are no changes in "heapify" function

    for (int i = size - 1; i >= start; i--) {
        swap_values(&arr[start], &arr[i]);
        heapify(arr, i, start);
    }
}

内省(introspection)排序:

template <typename T>
void introS(T* arr, int left, int right, int maxdepth) {
    if ((right - left) < 16)
        insertion_sort(arr, left, right + 1);
    else if (maxdepth == 0)
        heap_sort(arr, left, right + 1);
    else {
        int pivot = quickS_part(arr, left, right);

        introS(arr, left, pivot - 1, maxdepth - 1);
        introS(arr, pivot + 1, right, maxdepth - 1);
    }
}