c - 使用快速排序获取数组的排序索引

Question

我已更改为快速排序代码以对我从 tutorialgatway.org 获得的 float 数组进行排序。但是我需要排序的索引。我知道可用于获取排序索引的 qsort 库函数，我可以实现它。但是，我想避免使用标准库(我知道这不是推荐)。不使用标准库的原因是我需要在一个循环中对大量数组进行排序，我需要使用 openMP 对其进行并行化，因此显式编写函数将允许我在一个循环中并行化快速排序函数循环。

/* C Program for Quick Sort */
#include <stdio.h>

void Swap(float *x, float *y) {
    float Temp;
    Temp = *x;
    *x = *y;
    *y = Temp;
}

void quickSort(float a[], int first, int last) {
    int i, j;
    int pivot;
    if (first < last) {
        pivot = first;
        i = first;
        j = last;
        while (i < j) {
            while (a[i] <= a[pivot] && i < last)
                i++;
            while (a[j] > a[pivot])
                j--;
            if (i < j) {
                Swap(&a[i], &a[j]);
            }
        }
        Swap(&a[pivot], &a[j]);
        quickSort(a, first, j - 1);
        quickSort(a, j + 1, last);
    }
}

int main() {
    int number, i;
    float a[100];
    printf("\n Please Enter the total Number of Elements  :  ");
    scanf("%d", &number);
    printf("\n Please Enter the Array Elements  :  ");
    for (i = 0; i < number; i++)
        scanf("%f", &a[i]);

    quickSort(a, 0, number - 1);
    printf("\n Selection Sort Result : ");
    for (i = 0; i < number; i++)  {
        printf(" %f \t", a[i]);
    }
    printf("\n");
    return 0;
}

如何在代码中返回排序后的索引？

Answer 1

需要生成一个从0到size-1的索引数组，然后根据数组值对索引数组进行排序。所以代码确实使用数组 [index[...]] 进行比较，并在索引 [...] 上进行交换。

另一种方法是生成一个从 &array[0] 到 &array[size-1] 的指针数组。对指针进行排序后，您可以使用以下方法将它们转换为索引:index[i] = pointer[i] - &array[0](可以对索引和指针使用 union )。

---

使用标准版本的 Hoare 分区方案根据 A[] 中的 float 对 I[] 中的索引数组进行排序的示例程序:

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

void QuickSort(float A[], size_t I[], size_t lo, size_t hi)
{
    if (lo < hi)
    {
        float pivot = A[I[lo + (hi - lo) / 2]];
        size_t t;
        size_t i = lo - 1;
        size_t j = hi + 1;
        while (1)
        {
            while (A[I[++i]] < pivot);
            while (A[I[--j]] > pivot);
            if (i >= j)
                break;
            t = I[i];
            I[i] = I[j];
            I[j] = t;
        }
        QuickSort(A, I, lo, j);
        QuickSort(A, I, j + 1, hi);
    }
}

#define COUNT (4*1024*1024)             // number of values to sort

int main(int argc, char**argv)
{
    int  r;                             // random number
    size_t i;

    float  * A = (float *)  malloc(COUNT*sizeof(float));
    size_t * I = (size_t *) malloc(COUNT*sizeof(size_t));

    for(i = 0; i < COUNT; i++){         // random floats
        r  = (((rand()>>4) & 0xff)<< 0);
        r += (((rand()>>4) & 0xff)<< 8);
        r += (((rand()>>4) & 0xff)<<16);
        r += (((rand()>>4) & 0xff)<<24);
        A[i] = (float)r;
    }

    for(i = 0; i < COUNT; i++)          // array of indexes
        I[i] = i;

    QuickSort(A, I, 0, COUNT-1);

    for(i = 1; i < COUNT; i++){
        if(A[I[i-1]] > A[I[i]]){
            printf("error\n");
            break;
        }
    }

    free(I);
    free(A);

    return(0);
}

---

此版本的快速排序通过仅使用分区较小一侧的递归来避免堆栈溢出。最坏情况下时间复杂度仍为 O(n^2)，但堆栈空间复杂度限制为 O(log(n))。

void QuickSort(float A[], size_t I[], size_t lo, size_t hi)
{
    while (lo < hi)
    {
        float pivot = A[I[lo + (hi - lo) / 2]];
        size_t t;
        size_t i = lo - 1;
        size_t j = hi + 1;
        while (1)
        {
            while (A[I[++i]] < pivot);
            while (A[I[--j]] > pivot);
            if (i >= j)
                break;
            t = I[i];
            I[i] = I[j];
            I[j] = t;
        }
        /* avoid stack overflow */
        if((j - lo) < (hi - j)){
            QuickSort(A, I, lo, j);
            lo = j+1;
        } else {
            QuickSort(A, I, j + 1, hi);
            hi = j;
        }
    }
}