-2

我正在尝试在数组上使用快速排序，但是我不完全确定我做错了什么。我的顺序应该是

-2 0 1 4 7 9 11 12 15

但是我得到：

0 1 4 7 15 12 11 9 -2

这是我的分区代码：

int partition( int* a, int left, int right)
{
    int pivot, leftPoint, rightPoint, temp;
    pivot = a[left];
    leftPoint = left;
    rightPoint = right + 1;

    while(rightPoint > leftPoint)
    {
        while(a[leftPoint] <= pivot && leftPoint <= right)
            leftPoint ++;
        while(a[rightPoint] > pivot)
            rightPoint --;
        temp = a[leftPoint]; 
        a[leftPoint] = a[rightPoint]; 
        a[rightPoint] = temp;
    }
    temp = a[left];
    a[left] = a[rightPoint];
    a[rightPoint] = temp;
    return rightPoint;
}

有人可以在这里帮助解释我的算法有什么问题吗？

编辑：这是我的初始数组：

7 12 1 -2 0 15 4 11 9

我称快速排序为

quicksort(a, 0, 8);

这是我的快速排序的实现：

void quickSort( int a[], int low, int high)
{
   int pivotPoint;
   if(low < high)
   {
       // divide and conquer
        pivotPoint = partition( a, low, high);
        quickSort( a, low, pivotPoint);
        quickSort( a, pivotPoint + 1, high);
   }
}
4

2 回答 2

1

看来您正在使用分区的第一个元素作为阈值。那么那么

leftPoint = left;
rightPoint = right + 1;

在这里你包括它。

temp = a[left];
a[left] = a[rightPoint];
a[rightPoint] = temp;

到这里结束你用分区中间交换它。您首先需要排除阈值，其次不要超出数组：

leftPoint = left+1;
rightPoint = right;

编辑您还应该检查阈值是否小于下一个元素并仅在它不正确时交换它：

if(a[left+1] < pivot) {
    temp = a[left];
    a[left] = a[rightPoint];
    a[rightPoint] = temp;
    rightPoint = left;
}

或者如果数组已经排序，则分区将失败。

（编辑结束）

作为一个小优化

    pivotPoint = partition( a, low, high);
    quickSort( a, low, pivotPoint);
    quickSort( a, pivotPoint + 1, high);

在这里您可以完全排除阈值：

    quickSort( a, low, pivotPoint-1);
于 2014-04-28T16:35:58.573 回答
0

有了额外的信息，问题几乎肯定在于：

rightPoint = right + 1;

当您进入 for 的分区循环时(a, 0, 8)，您正在a[9]与枢轴值进行比较，这是一个坏消息，因为有效索引是a[0]to a[8]。

这是您转换为 SSCCE 的代码（简短、独立、正确的示例）：

#include <stdio.h>
#include <assert.h>

static
int partition(int *a, int left, int right)
{
    int pivot, leftPoint, rightPoint, temp;
    pivot = a[left];
    leftPoint = left;
    rightPoint = right + 1;

    while (rightPoint > leftPoint)
    {
        while (a[leftPoint] <= pivot && leftPoint <= right)
            leftPoint++;
        while (a[rightPoint] > pivot)
            rightPoint--;
        assert(a[leftPoint] != -99 && a[leftPoint] != +99);
        assert(a[rightPoint] != -99 && a[rightPoint] != +99);
        assert(leftPoint >= left && leftPoint <= right);
        assert(rightPoint >= left && rightPoint <= right);
        temp = a[leftPoint];
        a[leftPoint] = a[rightPoint];
        a[rightPoint] = temp;
    }
    temp = a[left];
    a[left] = a[rightPoint];
    a[rightPoint] = temp;
    return rightPoint;
}

static
void quickSort( int a[], int low, int high)
{
    int pivotPoint;
    if (low < high)
    {
        // divide and conquer
        pivotPoint = partition( a, low, high);
        quickSort( a, low, pivotPoint);
        quickSort( a, pivotPoint + 1, high);
    }
}

int main(void)
{
    int aplus[] =
    {
        +99, +99, +99,
        7, 12, 1, -2, 0, 15, 4, 11, 9,
        -99, -99, -99
    };
    int *a = aplus + 3;

    quickSort(a, 0, 8);
    return 0;
}

运行时，会触发其中一个断言：

Assertion failed: (a[rightPoint] != -99 && a[rightPoint] != +99),
    function partition, file partn.c, line 19.
于 2014-04-28T16:32:15.723 回答