2

我对编程相当陌生，并且已经学习了一段时间的排序算法。我已经在 C 中实现了下面的快速排序。它使用三个分区的中值来选择枢轴。代码的问题是每次我运行它时，应该是排序数组的中值/中间值的元素是未排序的，即它出现在其他地方。这是代码：

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

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
    return ;
}

int median3(int a[], int left, int right)//Uses median of three partitioning technique
{
    int center = (left + right)/2;
    if (a[center] < a[left]) 
        swap(&a[left],&a[center]);
    if (a[right] < a[left])
        swap(&a[left],&a[right]);
    if (a[right]< a[center])
        swap(&a[center],&a[right]);

    swap(&a[center], &a[right - 1]);//since the largest is already in the right.
    return a[right - 1];
}

void quicksort(int a[], int left, int right)
{
  if (left < right) {
    int pivot = median3(a,left,right);
    int i = left;
    int j = right - 1;
    for ( ; ;) {
        while(a[++i]<pivot) {} 
        while(pivot<a[--j]) {} 
        if ( i < j)
            swap(&a[i],&a[j]);
        else
            break ;
    }
    swap(&a[i],& a[right -1]);
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
  }
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {8,1,4,9,6,3,5,2,7,0};
    quicksort(a,0,9);
    for ( i = 0 ; i < 10 ; i++)
        printf("%d\n",a[i]);
    return 0;
}
4

1 回答 1

1

Watch out for the edge case, where left == right - 1:

void quicksort(int a[], int left, int right)
{
  if (left < right) {
    int pivot = median3(a,left,right);
    if (left == right - 1) return;  // only two elements, already sorted by median3()
    int i = left;
    int j = right - 1;

http://ideone.com/X5Ydx

于 2012-05-22T09:33:10.467 回答