#3708. 快速排序

快速排序

这里给你了一份快速排序相关函数的代码,它需要实现对 aa 数组下标 lrl\sim r 之间的元素进行 从大到小 排序的功能。你需要补全这个代码。

int qsort(int a[], int l, int r) {
    int i = l, j = r;
    int x = ①;
    while (i <= j) {
        while (i <= j && ②) {
            i++;
        }
        while (i <= j && ③) {
            j--;
        }
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (i < r) {
        qsort(a, i, r);
    }
    ④ {
        qsort(⑤);
    }
}

① 处 不应填 {{ select(1) }}

  • l
  • a[l]
  • a[r]
  • a[(l + r) >> 1]

② 处应填 {{ select(2) }}

  • a[i] > x
  • a[i] >= x
  • a[i] < x
  • a[i] <= x

③ 处应填 {{ select(3) }}

  • a[j] > x
  • a[j] >= x
  • a[j] < x
  • a[j] <= x

④ 处应填 {{ select(4) }}

  • else
  • if (l < j)
  • else if (l < j)
  • else if (l <= j)

⑤ 处应填 {{ select(5) }}

  • qsort(a, l, j)
  • qsort(a, l, j + 1)
  • qsort(a, l, j - 1)
  • qsort(a, j, i)