使用指针快速排序结构数组

Question

我的作业是使用指向数组第一个和最后一个元素的指针对结构数组进行快速排序。这是结构-

typedef struct Bus {
int number, distance, time; } Bus;

在程序的某个时刻，我有一个由这些结构的用户定义数量组成的数组。我的目标是按时间（从最低到最高）对数组进行排序。我需要填写的功能是-

void swap(Bus *a, Bus *b)    
void quick_sort (Bus *start, Bus *end) 
Bus *partition (Bus *start, Bus *end)

这是我的实现-

void swap(Bus *a, Bus *b)
{
  Bus tmp = *a;
  *a = *b;
  *b = tmp;
}

void quick_sort (Bus *start, Bus *end)
{
  long long n = end - start;
  if (n > 2)
  {
    Bus * pivot = partition (start, end);
    quick_sort (start, (end-1));
    quick_sort ((start+1), end);
  }

}

Bus *partition (Bus *start, Bus *end)
{
  long long n = end - start;
  int pivot = (end -1)->time;
  int i = start->time;
  int j = (end - 1)->time;
  for(;;)
  {
    
  }
}

我已经走到这一步了，不知道如何继续。我会感谢你的帮助。

edit- 这就是我从 main- quick_sort(arr, (arr + num_of_lines)) 调用函数的方式，当 num_of_lines 是数组的大小时。

Answer 1

首先，你的quick_sort是错误的。它应该是这样的：

void quick_sort(Bus *start, Bus *end)
{
    long long n = end - start;
    if (n >= 2)
    {
        Bus *pivot = partition(start, end);
        quick_sort(start, pivot++);
        quick_sort(pivot, end);
    }
}

注意长度条件。您应该只跳过长度为 0 或 1 而不是 2 的分区。并注意在第一次递归调用中对主元索引的 post-increment 调整。这可确保后续递归不包含您不想包含在递归中的一个元素：主元索引值。

就分区函数而言，也是错误的。它应该看起来像这样（我假设您使用的是 Lomuto Partition Scheme:

int *partition(Bus *beg, Bus *end)
{
    long len = end - beg;
    if (len < 2)
        return beg;

    Bus *last = end-1;
    Bus *pvt = beg;
    for (;beg != last; ++beg)
    {
        if (beg->time < last->time)
            swap(pvt++, beg);
    }    
    swap(pvt, last);

    return pvt;
}

使用指针快速排序结构数组

quick sorting an array of structs using pointers

c

pointers

quicksort