只有两个参数的快速排序

Question

如何构造一个以数组和数组长度作为两个参数的快速排序算法？

即：

void quick_sort(int A[], int n)

像这样。

但是，我只熟悉用 3 个参数、一个数组、最低索引和最高索引编写快速排序。

下面的 Quicksort 函数有 3 个参数，arr、l 和 h。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

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

int partition(int arr[], int l, int h) {
    int pivot = arr[l];
    int i = l;
    int j = h;

    while (i < j) {

        while (arr[i] <= pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i < j) {
            swap(&arr[j], &arr[i]);
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

void quickSort(int arr[], int l, int h) {
    if (l < h) {
        int j = partition(arr, l, h);
        quickSort(arr, l, j - 1);
        quickSort(arr, j + 1, h);
    }
}

但是，我需要编写一个只有两个参数的 QuickSort 实现。

如何编写进行相同排序的函数？也就是说，我们只有 n 的长度，而上面完整的快速排序算法有 l 和 h 作为参数。

Answer 1

很多代码为实际工作函数提供了一个很好的接口。例如，快速排序算法可能将其自身呈现为：

void quickSort( int * xs, int n );

但实现为：

static int partition( int * xs, int left, int right )
{
  ...
}

static void quickSort_( int * xs, int left, int right )
{
  ...
}

void quickSort( int * xs, int n )
{
  quickSort_( xs, 0, n );
}

注意实际的主力函数是如何static 到用户看不到它们的库。

只有两个参数的快速排序

QuickSort with only two arguments

c

arrays

sorting

quicksort