c - 使用堆栈迭代快速排序

Question

嗨，有人可以帮我解决我的代码吗，我不确定我哪里出错了 这是使用堆栈的迭代快速排序，数组是通过使用 void ** 指针传递的

int partition(void **A, int n, void *pivot){
    void * temp;
    int left = 0,j = 0;
    int right = n-1;
    int i = left;
    for (j=left;j<right;j++){
        if ((long)A[j] < (long)pivot){
            i++;
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    temp = A[i+1];
    A[right] = A[i+1];
    A[i+1] = temp;
    return i+1;
}
void myQuicksort(void **A, int n) {
    Stack *s = stack_new();     /*making new stack and allocating memory*/
    stack_push(s,(int*)0);      /*pushing left and then right*/
    stack_push(s,(int*)(n-1));
    while (!stack_isEmpty(s)){
        int right = (int)stack_pop(s);  /*poping return right then left*/
        int left = (int)stack_pop(s);
        if (right-left >=1){
            int pivot = (right+left)/2;  /* taking middle element as pivot */
            int p = partition(A+left , right-left+1 , A[pivot]);/*getting partition index*/
            stack_push(s, (int*)left);  
            stack_push(s, (int*)(p-1));
            stack_push(s,(int*)(p+1));
            stack_push(s,(int*)right);
            }
        }
    }

Answer 1

显然这就是你想要实现的快速排序算法 http://en.wikipedia.org/wiki/Quicksort#Algorithm

首先是一个方便的函数，用于将 A 中的两个指针交换为 long。

void swap(long **A, int i, int j)
{
   long *temp = A[i];
   A[i] = A[j];
   A[j] = temp;
}

配分函数如下。

请注意，您的代码缺少第一次交换。如果选择 hi 作为数据透视索引，则不需要它。但这不是你所做的。

另请注意，您对 i (storeIndex) 进行了预增量，这是一个错误。您应该首先进行交换，然后增加 i。我通过使用后增量将交换和增量合并在一条指令中。因此交换 i+1 并在最后返回 i+1 是错误的。

int partition(long **A, int lo, int hi)
{
    int pivotIndex = (hi+lo)/2, storeIndex = lo, i;
    long pivotValue = *A[pivotIndex];

    swap(A, pivotIndex, hi);
    for (i = lo; i < hi; ++i)
        if (*A[i] < pivotValue)
            swap(A, i, storeIndex++); /* Note: post increment of storeIndex */
    swap(A, storeIndex, hi);
    return storeIndex;
}

你的函数 我不希望在 11 点举行的航空 session 上不负责任的销售。 myQuickSort 然后变为如下。 请注意，您的堆栈现在必须存储 int (索引)而不是 int*。

void myQuicksort(void **A, int n) 
{
    int lo, hi, p;
    Stack *s = stack_new();     /* making new stack and allocating memory */
    stack_push(s, 0);      /* pushes initial lo and hi values */
    stack_push(s, n-1);    
    while (!stack_isEmpty(s))
    {
        hi = stack_pop(s);  
        lo = stack_pop(s);
        if (lo < hi)
        {
            p = partition(A, lo, hi);
            stack_push(s, lo);  
            stack_push(s, p-1);
            stack_push(s, p+1);
            stack_push(s, hi);
        }
    }
}

此代码尚未经过测试，因为我手头没有堆栈和数组。

为了使用此代码，您必须修复堆栈以便它存储整数。

我更改了你的变量名并使用 hi 和 lo 而不是你的方法，因为这样你只在堆栈上存储整数值。它更简单、更清晰。

更新:

由于这里强加了partition()的签名，所以这是一个新的代码提案。 这个签名的问题是你不知道主元存储在A中的什么位置。当partition()结束时，主元值必须存储在A[i]中。所以我们必须在开始分区之前找到它并将其存储在A[right]中。

int partition(void **A, int n, void *pivot){
    void * temp;
    int left = 0, j = 0;
    int right = n-1;
    int i = left;

    // locate the pivot
    for (j = 0; j < n; ++j)
        if (*(long*)A[j] == *(long*)pivot)
            break;

    // swap it with the right most value in A
    temp = A[j];
    A[j] = A[right];
    A[right] = temp;

    // do the partition
    for (j = 0; j < right; j++){
        if (*(long*)A[j] < *(long*)pivot){
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++; // post increment i
        }
    }

    // store the pivot in place
    temp = A[i];
    A[right] = A[i];
    A[i] = temp;

    // return the index of the pivot
    return i;
}

这是另一种可能的实现

int partition(void **A, int n, void *pivot){
    void * temp;
    int left = 0, j = 0;
    int right = n-1;
    int i = left;

    // do the partition
    for (j = 0; j < n; j++){
        if (*(long*)A[j] < *(long*)pivot){
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++; // post increment i
        }
    }
    // At this stage the pivot is somewhere in the range A[i] to A[right]

    // Lets find it and put it in A[i] if it's not already there
    if (*(long*)A[i] != *(long*)pivot){
        for (j = i+1; j < n; ++j){
            if (*(long*)A[j] == *(long*)pivot){
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                break;
            }
        }
    }

    // return the index of the pivot
    return i;
}