c - 如何在不使用循环的情况下编写排序函数？

Question

我正在尝试编写一个完全没有循环的递归排序函数。

void insertionSortRecursive(int arr[], int n)
{
    if (n <= 1)
        return;

    insertionSortRecursive( arr, n-1 );

    int last = arr[n-1];
    int j = n-2;


    while (j >= 0 && arr[j] > last)
    {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = last;
}

有没有办法摆脱 while 循环并仍然使这个函数工作？

Answer 1

使用 here 中的以下代码(使用另一个递归函数删除 while):

void insertInOrder( int element,int *a, int first, int last)
{
    if (element >= a[last])
        a[last+1] = element;
    else if (first < last)
    {
        a[last+1] = a[last];
        insertInOrder(element, a, first, last-1);
    }
    else // first == last and element < a[last]
    {
        a[last+1] = a[last];
        a[last] = element;
    }
}
void insertion_sort_recur(int *arr, int first, int last)
{
    if(first < last)
    {
        insertion_sort_recur(arr, first, last-1); // avoids looping thru arr[0..last-1]
        insertInOrder(arr[last], arr, first, last-1); // considers arr[last] as the first element in the unsorted list
    }
}   
void main()
{
    int A[]={5,3,2,4,6,1};
    insertion_sort_recur(A,0,5);
}