c - 查找无序数组的排序版本的 N 个连续元素的最佳方法是什么？

Question

例如:我有一个包含 10 个元素的未排序列表 A。我需要从 i 到 A 的排序版本的 i+k-1 的 k 个连续元素的子列表。

Example:  
Input: A { 1, 6, 13, 2, 8, 0, 100, 3, -4, 10 }  
       k = 3  
       i = 4  
Output: sublist B { 2, 3, 6 }

Answer 1

如果指定了 i 和 k，您可以使用特殊版本的快速排序，在该版本中您停止对落在 i 之外的数组部分进行递归.. i+k 范围。如果数组可以修改，则就地执行此部分排序，如果数组不能修改，则需要复制一份。

这是一个例子:

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

// Partial Quick Sort using Hoare's original partition scheme
void partial_quick_sort(int *a, int lo, int hi, int c, int d) {
    if (lo < d && hi > c && hi - lo > 1) {
        int x, pivot = a[lo];
        int i = lo - 1;
        int j = hi;

        for (;;) {
            while (a[++i] < pivot)
                continue;

            while (a[--j] > pivot)
                continue;

            if (i >= j)
                break;

            x = a[i];
            a[i] = a[j];
            a[j] = x;
        }
        partial_quick_sort(a, lo, j + 1, c, d);
        partial_quick_sort(a, j + 1, hi, c, d);
    }
}

void print_array(const char *msg, int a[], int count) {
    printf("%s: ", msg);
    for (int i = 0; i < count; i++) {
        printf("%d%c", a[i], " \n"[i == count - 1]);
    }
}

int int_cmp(const void *p1, const void *p2) {
    int i1 = *(const int *)p1;
    int i2 = *(const int *)p2;
    return (i1 > i2) - (i1 < i2);
}

#define MAX 1000000

int main(void) {
    int *a = malloc(MAX * sizeof(*a));
    clock_t t;
    int i, k;

    srand((unsigned int)time(NULL));

    for (i = 0; i < MAX; i++) {
        a[i] = rand();
    }
    i = 20;
    k = 10;
    printf("extracting %d elements at %d from %d total elements\n",
           k, i, MAX);
    t = clock();
    partial_quick_sort(a, 0, MAX, i, i + k);
    t = clock() - t;
    print_array("partial qsort", a + i, k);
    printf("elapsed time: %.3fms\n", t * 1000.0 / CLOCKS_PER_SEC);

    t = clock();
    qsort(a, MAX, sizeof *a, int_cmp);
    t = clock() - t;
    print_array("complete qsort", a + i, k);
    printf("elapsed time: %.3fms\n", t * 1000.0 / CLOCKS_PER_SEC);

    return 0;
}

使用包含 100 万个随机整数的数组运行此程序，从偏移量 20 开始提取已排序数组的 10 个条目，得到以下输出:

extracting 10 elements at 20 from 1000000 total elements
partial qsort: 33269 38347 39390 45413 49479 50180 54389 55880 55927 62158
elapsed time: 3.408ms
complete qsort: 33269 38347 39390 45413 49479 50180 54389 55880 55927 62158
elapsed time: 149.101ms

它确实比对整个数组排序快得多(20x 到 50x)，即使选择一个简单的主元也是如此。尝试多次运行，看看时间如何变化。