为什么更改随机数生成器会更改运行 C 中快速排序的时间

Question

我用 C 编写了一个快速排序实现。在第一个循环中更改 rand 函数范围（使用余数）会显着改变算法的运行时间。现在，该算法需要 43 秒。将范围从 100 更改为 10000 可减少运行 0.9 秒。

这是为什么？

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void quick_sort(int array[], int low, int high);
int partition(int array[], int low, int high);
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


int main(void)
{
    const int len = 1000000;
    srand(time(NULL));
    int array[len];

    puts("Populating the array...\n");
    for(int i = 0; i < len; i++)
        array[i] = rand() % 100; // Changing this line dramatically reduce the running time

    puts("|Now sorting the array...|\n");

    quick_sort(array, 0, len-1);

    /*for(int i = 0; i < len; i++)*/
        /*printf("%d ", array[i]);*/
}


void quick_sort(int array[], int low, int high)
{
    int j;

    if(low < high)
    {
        j = partition(array, low, high);
        quick_sort(array, low, j-1);
        quick_sort(array, j+1, high);
    }
}

int partition(int array[], int low, int high)
{
    int pivot    = array[high];
    int leftwall = low-1;

    for(int i = low; i < high; i++)
    {
        if(array[i] <= pivot)
        {
            ++leftwall;
            swap(&array[leftwall], &array[i]);
        }
    }

    swap(&array[leftwall+1], &array[high]);

    return ++leftwall;
}

Answer 1

我的猜测是，在对数组进行分区时，您最终会移动大量重复值。当您仅从 100 个选项中选择随机数时，一百万个元素的数组每个值大约有 10,000 个。由于 array[i] <= pivot 比较，您似乎会在每次调用 partition 时交换它们。例如，当您快要完成并且分区中只有两个不同的值时，它仍然有大约 20,000 个元素......

为什么更改随机数生成器会更改运行 C 中快速排序的时间

Why changing random number generator changes running time of quick sort in C

c

quicksort

为什么更改随机数生成器会更改 运行 C 中快速排序的时间

Why changing random number generator changes running time of quick sort in C

c

quicksort

为什么更改随机数生成器会更改运行 C 中快速排序的时间