使用Lomuto算法进行分区的快速排序函数中“pi+1”语句如何消除尾部调用？

Question

/* 尾调用消除后的快速排序 */

#include<stdio.h>

交换两个元素的实用函数

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/* 该函数将最后一个元素作为基准，放置 排序后的枢轴元素位于其正确位置 数组，并放置所有较小的（小于枢轴） 到枢轴的左侧，所有更大的元素到右侧 的枢轴。它使用 Lomuto 分区算法。 */

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    `// pivot`
    int i = (low - 1);  `// Index of smaller element`

    for (int j = low; j <= high- 1; j++)
    {
        `// If the current element is smaller than or equal to pivot `
        if (arr[j] <= pivot)
        {
            i++;    `// increment index of smaller element`
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* 实现QuickSort的主要函数 arr[] --> 要排序的数组， 低 --> 起始索引， 高 --> 结束指数 */

void quickSort(int arr[], int low, int high)
{
    while (low < high)
    {
        `/* pi is partitioning index, arr[p] is now at right place */`
        int pi = partition(arr, low, high);

        `// Separately sort elements before partition and after partition`
        quickSort(arr, low, pi - 1);

        low = pi+1;
    }
}

打印数组的函数

void printArray(int arr[], int size)
{
    for (int i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

测试上述功能的驱动程序

int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Answer 1

“pi+1”语句如何消除快速排序函数中的尾部调用

事实并非如此。所有主流 x86 编译器都无法从代码中展开递归。例如 gcc -O3 (godbolt):

quickSort:
        cmp     esi, edx
        jge     .L6
        push    r13
        mov     r13, rdi
        push    r12
        mov     r12d, edx
        push    rbp
        mov     ebp, esi
        push    rbx
        sub     rsp, 8
.L3:
        mov     esi, ebp
        mov     edx, r12d
        mov     rdi, r13
        call    partition
        mov     esi, ebp
        mov     rdi, r13
        mov     ebx, eax
        lea     edx, [rax-1]
        call    quickSort     // recursive call
        lea     ebp, [rbx+1]
        cmp     r12d, ebp
        jg      .L3
        add     rsp, 8
        pop     rbx
        pop     rbp
        pop     r12
        pop     r13
        ret

Answer 2

一个简单的快速排序实现将有两次递归调用。

来自维基百科：

algorithm quicksort(A, lo, hi) is 
  // Ensure indices are in correct order
  if lo >= hi || lo < 0 then 
    return
    
  // Partition array and get the pivot index
  p := partition(A, lo, hi) 
      
  // Sort the two partitions
  quicksort(A, lo, p - 1) // Left side of pivot
  quicksort(A, p + 1, hi) // Right side of pivot

第二个是尾部调用，因此可以被消除。这是在您发布的代码中完成的（通过手动重构）。

第一个无法消除（不引入向量/队列/堆栈）。