0

我是一个新手 C 程序员，并且一直在研究这个算法很长时间。我非常沮丧，因为我无法获得正确的非递减排序序列。

欢迎所有帮助。提前致谢。

这是我的代码：

#include <stdio.h>
#include <conio.h>

int swap(short* a, short fst , short scnd){
    short temp  = a[fst] ;
    a[fst]          = a[scnd] ;
    a[scnd]         = temp ;

    return 0 ;
}

int div(short* a ,short p,short middle ,short r){
    while( p < r ){
        if( p < middle ){       
            if( a[p]      > a[middle] ){
                swap(a ,p ,middle) ; 
            }
            p++ ; 
        }
        if( middle < r ){
            if( a[middle] > a[r] ){
                swap(a ,middle , r) ;      
            }         
            r-- ;
        }
    }

    return 0 ;
}

int fast(short* a , short p , short r){
    if( p < r){
        int middle = (p+r)/2 ;
        div(a, p, middle ,r ) ;
        fast(a, p ,middle-1 ) ;
        fast(a ,middle+1 ,r);
    }
}

int main(){
    short n ,i ;
    scanf("%hd",&n);
    short a[n+1] ;
    for(i=1 ; i<=n ; i++ ){
        scanf("%hd",&a[i]);
    }

    fast(a ,1 ,n ) ;
    i=1;
    while(i<=n){
        printf("%hd " , a[i]);
        i++ ;
    }
    getch() ;
    return 0 ;
}
4

3 回答 3

1

错误在于 div 函数本身，它没有遵循 QuickSort 逻辑。你可以在这里找到工作代码Quicksort algorithm

我建议复制粘贴代码并从它的编码标准中获得灵感，包括评论:)

于 2012-08-29T18:32:50.930 回答
0

我会更改您的 div 函数以返回分区的结果索引。这样，在 fast() 函数中，您可以在分区点的两侧进行递归。这会清理逻辑，并且应该可以轻松地单独测试 div 函数并找到逻辑中的弱点（它肯定在 div() 函数中）。

看起来目前您的代码假设分区总是发生在中间，而快速排序并非总是如此（实际上这是快速排序的微妙点之一）。

这是一个示例分区函数：

// please forgive any C-syntax errors not my best language
// low and high indicate a segment of the array to partition
// returns the index between low and high which serves as
// the partition point
int partition(short a[], int low, int high){
  int partition = low;
  int pivot = high;  // sub-optimal when a is already sorted
  for(int i=low; i<high; i++){
    if(a[i] < a[pivot]){
      swap(&a[i], &a[partition]);
      partition++;
    }
  }
  // places the pivot into its final sorted position at partition
  swap(&a[partition], &a[pivot]);
  return partition;
}

这可以递归使用如下

sort(short a[], int low, high){
  if(high-low > 0){
    int partition = partition(a, low, high);
    // recurse to left and right of partition
    sort(a, low, partition-1);
    sort(a, partition+1, high);
  }
}
于 2012-08-29T20:51:43.220 回答
0

一个数据序列：
索引：1 2 3 4 5 6 7
数据：1 2 0 10 8 4 5
中间：(1 + 7) / 2 = 4
a[中间]=10
你的功能 div 想要什么？

于 2012-08-29T22:42:50.190 回答