带随机枢轴的稀疏矩阵原地快速排序C实现修正求助

需要实现随机枢轴的快速排序算法处理大型稀疏矩阵，无法承受最坏时间复杂度。现有代码是基于首个元素为枢轴的版本修改而来，已适配稀疏矩阵（按「行索引、列索引」排序），但处理近乎有序矩阵时运行极慢；尝试启用随机枢轴（取消注释对应代码）后，算法无法正确排序数据，请求修复。

原排序代码：

void quicksortSparseMatrix(struct sparsematrix *matrix,int first,int last){
    
    int i, j, pivot, temp_I, temp_J;
    double temp_val;
    

    if(first<last){
        pivot=first;            //(rand() % (last - first + 1)) + first;
        
        i=first;
        j=last;     

        while(i<j){
            while(lessEqual(matrix,i, pivot)&&i<last)
                i++;
            while(greater(matrix,j, pivot))
                j--;
            if(i<j){   
                temp_I = matrix->I[i];
                temp_J = matrix->J[i]; 
                temp_val = matrix->val[i];
                matrix->I[i] = matrix->I[j];
                matrix->J[i] = matrix->J[j];
                matrix->val[i] = matrix->val[j];
                matrix->I[j]=temp_I;
                matrix->J[j]=temp_J;
                matrix->val[j]=temp_val;
            }
        
        }


    temp_I = matrix->I[pivot];
    temp_J = matrix->J[pivot]; 
    temp_val = matrix->val[pivot];
    matrix->I[pivot] = matrix->I[j];
    matrix->J[pivot] = matrix->J[j];
    matrix->val[pivot] = matrix->val[j];
    matrix->I[j]=temp_I;
    matrix->J[j]=temp_J;
    matrix->val[j]=temp_val;
    
    quicksortSparseMatrix(matrix,first,j-1);
    quicksortSparseMatrix(matrix,j+1,last);
    }
}

稀疏矩阵结构体定义：

struct sparsematrix {
    int M, N, nz;   
    int *I, *J;
    double *val;
}; 

问题出在随机选枢轴后，原代码的分区逻辑没有适配新的枢轴位置。只需在选定随机枢轴后，先将其与first位置的元素交换，让后续分区逻辑保持和原代码一致即可：

#include <stdlib.h> // 确保引入rand()所需头文件

void quicksortSparseMatrix(struct sparsematrix *matrix,int first,int last){
    
    int i, j, pivot, temp_I, temp_J;
    double temp_val;
    

    if(first<last){
        // 1. 随机选取枢轴位置
        pivot = (rand() % (last - first + 1)) + first;
        
        // 2. 将随机枢轴元素交换到first位置，适配原分区逻辑
        temp_I = matrix->I[pivot];
        temp_J = matrix->J[pivot]; 
        temp_val = matrix->val[pivot];
        matrix->I[pivot] = matrix->I[first];
        matrix->J[pivot] = matrix->J[first];
        matrix->val[pivot] = matrix->val[first];
        matrix->I[first] = temp_I;
        matrix->J[first] = temp_J;
        matrix->val[first] = temp_val;
        // 更新pivot为first，后续逻辑和原代码一致
        pivot = first;
        
        i=first;
        j=last;     

        while(i<j){
            while(lessEqual(matrix,i, pivot)&&i<last)
                i++;
            while(greater(matrix,j, pivot))
                j--;
            if(i<j){   
                temp_I = matrix->I[i];
                temp_J = matrix->J[i]; 
                temp_val = matrix->val[i];
                matrix->I[i] = matrix->I[j];
                matrix->J[i] = matrix->J[j];
                matrix->val[i] = matrix->val[j];
                matrix->I[j]=temp_I;
                matrix->J[j]=temp_J;
                matrix->val[j]=temp_val;
            }
        
        }


    temp_I = matrix->I[pivot];
    temp_J = matrix->J[pivot]; 
    temp_val = matrix->val[pivot];
    matrix->I[pivot] = matrix->I[j];
    matrix->J[pivot] = matrix->J[j];
    matrix->val[pivot] = matrix->val[j];
    matrix->I[j]=temp_I;
    matrix->J[j]=temp_J;
    matrix->val[j]=temp_val;
    
    quicksortSparseMatrix(matrix,first,j-1);
    quicksortSparseMatrix(matrix,j+1,last);
    }
}

• 随机选枢轴后，必须将枢轴元素交换到first位置：原代码的分区逻辑全程以pivot位置（初始为first）的元素作为比较基准，直接用随机位置的话，基准元素位置未对齐，会导致分区逻辑混乱，排序失效。交换后，后续的分区、递归逻辑可以完全复用原代码的逻辑，同时实现随机枢轴的效果。
• 注意在调用该排序函数前，需要初始化随机数生成器，比如在主函数中调用srand(time(NULL));，否则每次运行的随机枢轴序列会完全相同，无法发挥随机枢轴避免最坏情况的作用。

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