学步园

    在快排中，这样的数组元素被称为枢轴——其前面的元素全都小于它（或大于），其后面的元素全都大于它（或小于）。如此，我们很容易想到，对于一个数组，如果其全部元素都可以被称为枢轴，那么，该数组就是一个已经排序好的数组。

    参考代码：

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

static int partition(void* arr, int(*cmp)(void*, void*), int left, int right, int size)
{
  char* tmp = (char*)malloc(size);
  memcpy(tmp, (char*)arr + left * size, size);
  while (left < right)
  {
    while (left < right && cmp((char*)arr + right * size, (char*)tmp) >= 0)--right;
    memcpy((char*)arr + left * size, (char*)arr + right * size, size);
    while (left < right && cmp((char*)arr + left * size, (char*)tmp) <= 0)++left;
    memcpy((char*)arr + right * size, (char*)arr + left * size, size);
  }
  memcpy((char*)arr + right * size, (char*)tmp, size);
  return right;
}

static void q_sort(void* arr, int(*cmp)(void*, void*), int left, int right, int size)
{
  if (right <= left)
    return;
  int part = partition(arr, cmp, left, right, size);
  q_sort(arr, cmp, left, part - 1, size);
  q_sort(arr, cmp, part + 1, right, size);
}

void quicksort(void* arr, int n, int(*cmp)(void*, void*), int size)
{
  q_sort(arr, cmp, 0, n - 1, size);
}