K&R习题实现字符串快速排序时Partition函数触发段错误如何解决

问题原因排查 #

1. 分区逻辑错误导致无限递归栈溢出（核心原因） #

你当前的Partition函数逻辑存在严重缺陷，会触发无限递归最终栈溢出，这是段错误的直接原因：

• 循环遍历范围包含了pivot所在的end下标，pivot和自身比较不会触发交换逻辑
• 遍历结束后没有把pivot元素交换到最终的排序位置，直接返回--Pindex会返回错误的分区下标，导致递归的边界永远无法收敛。比如你给出的测试用例第一次调用Partition会返回-1，接下来会重复触发Quicksort(Lines, 0, 2)的调用，直到栈空间耗尽触发段错误。

2. 基础代码规范缺失 #

• 缺少必要的头文件声明：使用printf需要包含<stdio.h>，使用strcmp需要包含<string.h>
• 缺少宏定义：MAXLINES没有定义会导致编译异常
• 缺少函数前置声明：如果函数定义在main之后，必须提前声明函数原型，否则旧标准C编译器会做隐式类型转换，导致参数传递错误访问非法地址。

修正方案 #

正确的Partition逻辑 #

int Partition( char *line[] , int start , int end )
{
    char *pivot = line[end];
    int Pindex = start;
    // 只遍历到end-1，跳过pivot本身
    for( int i = start ; i < end ; i++ ) {
        if( strcmp( line[i] , pivot ) < 0 ) {
            Swap( line , i , Pindex ) ;
            Pindex++ ;
        }
    }
    // 把pivot交换到最终的正确位置
    Swap(line, Pindex, end);
    // 直接返回pivot的下标
    return Pindex ;
}

完整可运行代码参考 #

#include <stdio.h>
#include <string.h>
// 定义MAXLINES宏
#define MAXLINES 1024

// 提前声明函数原型
void Swap( char *line[] , int index1 , int index2 );
int Partition( char *line[] , int start , int end );
void Quicksort( char *line[] , int start , int end );

int main( int argc , char *argv[] )
{
    char *Lines[MAXLINES] ;
    Lines[0] = "Premier League is the best .\n" ;
    Lines[1] = "Manchester United \n" ;
    Lines[2] = "KOlkata \n" ;

    Quicksort( Lines , 0 , 2 ) ;
    for(int i = 0 ; i <3 ; i++ ) 
        printf("%s" , Lines[i] ) ;
    return 0 ;
}

void Quicksort( char *line[] , int start , int end )
{
    if( start >= end )
        return ;
    else {
        int Pindex = Partition( line , start , end ) ;
        Quicksort( line , start , Pindex - 1 ) ;
        Quicksort( line , Pindex + 1 , end ) ;
    }
}

int Partition( char *line[] , int start , int end )
{
    char *pivot = line[end];
    int Pindex = start;
    for( int i = start ; i < end ; i++ ) {
        if( strcmp( line[i] , pivot ) < 0 ) {
            Swap( line , i , Pindex ) ;
            Pindex++ ;
        }
    }
    Swap(line, Pindex, end);
    return Pindex ;
}

void Swap( char *line[] , int index1 , int index2 )
{
    char *temp = line[index1];
    line[index1] = line[index2];
    line[index2] = temp;
}

内容的提问来源于stack exchange，提问作者ChucklesDroid