如何通过Quicksort对链接列表中的数据进行排序？

Question

我想通过Quicksort对链接列表中的数据进行排序。这是我的代码：

struct stu
{

    int id; 
    char name[100]; 
    int score; 
    stu* next;
}head;

int address(stu* StudentList)
{

    //return the index of data
    int index = 0;
    stu* test = head;
    for (index = 0; test != StudentList; temp++)
    {
        test = test->next;
    }
    return index;
}

stu* section(int low)
{

    //Classification discussion on data
    stu* StudentList1=head;
    for (int i = 0; i < low; i++)
    {
        StudentList1 = StudentList1->next;
    }
    return StudentList1;
}

void swap(stu *Student1,stu *Student2)
{

    int t_id = 0, t_score = 0;
    char t_name[10] = "000";
    //exchange id 
    t_id = Student1->id;
    Student1->id = Student2->id;
    Student2->id = t_id;
    //exchange name
    strcpy(t_name, Student1->name);
    strcpy(Student1->name, Student2->name);
    strcpy(Student2->name, t_name);
    //exchange score
    t_score = Student1->score;
    Student1->score = Student2->score;
    Student2->score = t_score;
}

void sort(int low, int high)
{

    stu* StudentList1 = head, * StudentList2 = StudentList1->next;
    if (low >= high)
        return;
    else 
    {
        StudentList1=section(low);
        StudentList2 = StudentList1->next;
        stu* key = StudentList1;
        int i;
        for (int i = 0; i <= (high - low) && StudentList2 != NULL; i++)
        {
            if (StudentList2->score >= key->score)
            {
                StudentList1 = StudentList1->next;
                swap(StudentList1, StudentList2);
            }
            StudentList2 = StudentList2->next;
        }
        swap(key, StudentList1);
        int temp = address(StudentList1);
        StudentList2 = head;
        for (i = 0; StudentList2->next!=NULL;StudentList2=StudentList2->next)
        {
            if (StudentList2->next->score <= StudentList2->score)
            {
                i++;
            }
        }
        high = temp - 1;
        low = temp + 1;
        if (i < num - 1)
        {
            sort(0, high);
            sort(low, num - 1);
        }
        return;
    } 
}

问题是程序处于无限循环中。我试图修改它，但没有帮助。所以我必须转向Stackoverflow。谢谢！

我刚刚修改了代码。但是仍然存在一些问题。当处理7个数据时，该程序可以正常运行。但是，在处理8个数据时，编译器在“ section”中告诉我堆栈溢出。希望您能指出问题所在。真诚的谢谢！

Answer 1

一个潜在的问题是此行：

            sort(0, high);

递归调用应至少比sort（lo，hi）小至少一个节点。可能还有其他问题。

假设这是一个类分配，我不确定在通常使用合并排序的情况下为什么选择quicksort作为对链表进行排序的方法。还可以选择通过重新排列节点中的数据来“排序”链接列表，而不是通过对链接列表中的节点重新排序来进行排序。由于问题未指定分配要求，因此我不确定目标是什么。

将索引用于链表是无效的。您可以使用基于指针的快速排序，例如：

void QuickSort(stu * lo, stu * hi);

调用代码或帮助函数将需要扫描列表以将quicksort调用设为hi。这是Lomuto分区方案的一种变体，可以将其转换成quicksort，通过交换数据（而不是交换节点，这需要跟踪先前要交换的节点）来对链表进行排序。变量j用于避免在通常为QuickSort（lo，i-1）的情况下使用i-1，因为单个链接列表中没有i-> prev。

void QuickSort(int a[], int lo, int hi)
{
    if(lo >= hi)
        return;
    int p = a[lo];
    int i = lo;
    int j = lo;
    for(int k = lo+1; k <= hi; k++){
        if(a[k] < p){
            j = i++;
            std::swap(a[k], a[i]);
        }
    }
    std::swap(a[i], a[lo]);
    QuickSort(a, lo, j);
    QuickSort(a, i+1, hi);
}

[您也可以考虑类似快速排序的方法，该方法在每个递归级别上创建3个列表，对节点进行排序而不是交换数据。这3个列表将是节点枢轴。递归将用于节点==的2个列表，然后将3个列表串联。