分析C中的快速排序

Question

我想要做的是获得下面所需的输出.我已经尝试在quicksort的开头打印,我得到了一些正确的值,但我觉得我的整个方法都没有用,所以我需要一些帮助.

level partitionNumber d [3a_spaces x1 x3 ... xn 3b_spaces]

地点:

level是递归的级别.

partitionNumber是用于创建分区的编号.

如果partitionNumber大于分区的元素,则d为'>',否则为'<'.

3a_space是在分区开始之前数组的每个元素的一组3个空格字符.

x1 x3 ... xn是分区中的数字集.注意:使用"%3d"格式描述符打印这些数字.

3b_spaces是分区结束后数组中每个元素的一组3个空格字符.

期望的输出:

1  0  [23 13 82 33 51 17 45 75 11 27 ]
2 51> [27 13 33 23 17 45 11          ]
3 23> [11 13 17                      ]
3 23> [11 13 17                      ]
3 23< [            33 45 27          ]
4 45> [            27 33             ]
4 45> [            27 33             ]
3 23< [            27 33 45          ]
2 51> [11 13 17 23 27 33 45          ]
2 51< [                        82 75 ]
2 51< [                        75 82 ]
1  0  [11 13 17 23 27 33 45 51 75 82 ]

我的输出:

1  0  [23 13 82 33 51 17 45 75 11 27 ]
2 51> [27 13 33 23 17 45 11          ]
3 23> [11 13 17                      ]
2 13> [11 13 17                      ]
3 23< [            33 45 27          ]
4 45> [            27 33             ]
3 27? [            27 33             ]
2 45> [            27 33 45          ]
1 23> [11 13 17 23 27 33 45          ]
2 51< [                        82 75 ]
1 82> [                        75 82 ]
0 51> [11 13 17 23 27 33 45 51 75 82 ]






 #include<stdio.h>

int inputLine[10];

void quicksort(int v[], int left, int right, int level, int previousPivotPoint, char d);

int main()
{
  int v[] = { 23, 13, 82, 33, 51, 17, 45, 75, 11, 27 };
  quicksort(v, 0, 9, 0, -1, ' ');



  return 0;
}

void swap(int v[], int i, int j)
{
  int temp;
  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
}

void quicksort(int v[], int left, int right, int level, int previousPivotPoint, char d)
{
  int i, last;

  level++;
  if (previousPivotPoint > v[left]) d = '>';
  else if (previousPivotPoint < v[left]) d = '<';


  if (left >= right)
  {
    level--;
    return;
  }
  if (previousPivotPoint == -1)
  {
    printf("%d  0  [", level);
  } else
  {
    printf("%d %d%c [", level, previousPivotPoint, d);
  }

  previousPivotPoint = v[(left + right) / 2];

  d = '?';
  for (i = 0; i < 10; i++)
  {
    if (i > right || i < left)
    {
      printf("   ");
    } else
    {
      printf("%d ", v[i]);
    }
  }
  printf("]\n");

  swap(v, left, (left + right) / 2);

  last = left;

  for (i = left + 1; i <= right; i++)
  {
    if (v[i] < v[left])
    {
      last++;
      swap(v, last, i);
    }
  }

  swap(v, left, last);
  quicksort(v, left, last - 1, level, previousPivotPoint, d);
  quicksort(v, last + 1, right, level, previousPivotPoint, d);
  level--;


  if (previousPivotPoint > v[left]) d = '>';
  else if (previousPivotPoint < v[left]) d = '<';
  printf("%d %d%c [", level, previousPivotPoint, d);
  previousPivotPoint = v[(left + right) / 2];


  for (i = 0; i < 10; i++)
  {
    if (i > right || i < left)
    {
      printf("   ");
    } else
    {
      printf("%d ", v[i]);
    }
  }
  printf("]\n");

}

Answer 1

没有时间太深入地研究您的代码，但这里有一些事情。

您应该做的第一件事就是10用 #define常量替换硬编码。

d您没有设置 的值，因此没有设置所有空格，这应该不足为奇。另外，为什么要d全球化？

您的打印循环应该遍历整个列表，因此括号中的部分将始终具有相同的大小。