C陣列分區

Question

我想在數組上使用快速排序，但是我不完全確定我在做什麼錯誤。我在訂單編號應當是

-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); 

這是實現我的quicksort：

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); 
    } 
} 

Answer 1

在有額外信息，問題幾乎肯定在於：

rightPoint = right + 1; 

當你進入分區環路(a, 0, 8)，你與樞軸價值，這是因爲有效的壞消息比較a[9]索引是a[0]到a[8]。

，這裏是你的代碼轉換爲SSCCE（Short, Self-Contained, Correct Example）：

#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. 

Answer 2

看來你正在使用作爲您的分區的第一個元素閾。那麼

leftPoint = left; 
rightPoint = right + 1; 

這裏包括它。

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

到此爲止您可以在中間與分區交換。首先需要排除門限，二不超越數組：

leftPoint = left+1; 
rightPoint = right; 

編輯您alsho應該檢查是否閾值小於下一個元素且僅當它不是真的掉它：

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

如果數組已經排序，分區將失敗。

（年底 編輯）

作爲LITTEL優化

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

在這裏，您可以排除門檻完全

：

quickSort(a, low, pivotPoint-1);