为什么这个快速排序看起来比 std::sort 快？

Question

为什么这个快速排序算法看起来比 std::sort 快？我已经检查以确保它实际上正在对数组进行排序。我还用相同迭代次数的空心 for 循环替换了两个排序调用，以测试时序基准并在那里检查了所有内容。

我也想知道我可以对快速排序进行哪些调整以使其递归更多次。也许某种可变内存管理？

#include <iostream>     
#include <vector>       
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <chrono>
using namespace std;
void quickSort(int*, int);
void fillRandom(int*, int,int b2);
int main() {
    //setup arrays
    int size = 100000;
    auto myints = new int[size];
    auto myints2 = new int[size];
    fillRandom(myints, size,10000);
    std::copy(myints, myints + size, myints2);

    //measurement 1
    auto t1 = std::chrono::high_resolution_clock::now();
    quickSort(myints, size);
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    std::cout << endl << "Execution 1 took: "<< duration << endl;

    //measurement 2
    t1 = std::chrono::high_resolution_clock::now();
    std::sort(myints2,myints2+size);
    t2 = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    std::cout << endl << "Execution 2 took: " << duration << endl;


    cout << "finished!";
    return 1;
}
void fillRandom(int* p, int size,int upTo) {
    srand(time(0));
    for (int i = 0;i < size;i++) {
        p[i] = rand() % upTo + 1;
    }
}
void quickSortSwap(int *p1, int*p2) {
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;

}
void quickSort(int* original, int len) {
    int split = *original;
    int greaterIndex = len - 1;
    int lesserIndex = 1;
    int* currentP;
    //rearrange stuff so smaller is left, bigger is right
    for (int i = 1;i < len;i++) {
        currentP = original + lesserIndex;
        //cout << *currentP << " compared to " << split << endl;
        if (*currentP <= split) {
            lesserIndex++;
        }
        else {
            //cout << "greater: " << *currentP <<endl;
            quickSortSwap(currentP, original + greaterIndex);
            greaterIndex--;
        }
    }

    //uhh, now we switch pivot element with the right most left side element. Adjust our left side length measurement accordingly.
    lesserIndex--;
    quickSortSwap(original, original + lesserIndex);
    greaterIndex++;
    //this point
    if (lesserIndex > 1) {
        quickSort(original, lesserIndex);
    }
    int greater_range = len - greaterIndex;
    if (greater_range > 1) {
        quickSort(original + greaterIndex, greater_range);
    }
}

https://rextester.com/AOPBP48224

Answer 1

Visual Studio 的 std::sort 有一些开销和一些您的程序没有的优化。您的程序基于 Lomuto 分区方案，而 std::sort 是单主元，3 分区 Hoare，如快速排序 + 用于小分区的插入排序。 3 个分区是 elements < pivot, elements == pivot, elements > pivot。如果没有重复值，则 3 分区排序只是一些开销。如果存在重复值，那么随着重复值数量的增加，Lomuto 变得更糟，而 Hoare 或 std::sort 变得更好。尝试使用 fillRandom(myints, size,10);并且您应该会看到 Lomuto 方法对性能的巨大影响，以及 std::sort().

的性能提升

Visual Studio的std::sort如果>=40个元素使用9的中位数，33到39个元素使用3的中位数，这降低了最坏情况的概率，并切换到插入排序对于 <= 32 个元素（这会加快速度）。为了减少堆栈开销，它对较小的分区使用递归，并循环回处理较大的分区。它有一个检查以避免最坏情况下的时间复杂度 O(n^2)，如果分区深度（“递归”）变得过多，则切换到堆排序。它使用迭代器而不是普通指针，但在发布模式下，我的印象是迭代器未经检查，实际上是指针。它还使用函数指针进行比较，默认为std::less，我不知道它是否被优化掉了。

为什么这个快速排序看起来比 std::sort 快？

Why does this quicksort appear to be faster than std::sort?

c++

algorithm

optimization

quicksort