C语言中一个简单、可移植且高效的快速排序实现
5.00/5 (12投票s)
C语言中一个简单、可移植且高效的快速排序实现
引言
我希望在这里提供一个公有领域的C语言快速排序算法实现，从头开始编写，任何人都可以使用而无需担心许可问题。
背景
每当我在互联网上寻找快速排序实现时，我总是被限制在简单、递归但不够高效的算法实现上。对于更符合生产质量的代码，我发现的唯一内容要么受到未知或限制性许可的保护。
该算法的性能相当好，与Linux和MacOS X中找到的标准qsort性能相似。我测试了一点代码以验证它没有错误。但是，我应该警告人们以自担风险使用它，因为测试覆盖范围仍然有限。如果有人发现其中有任何问题，欢迎通知我。
Using the Code
下面介绍的代码执行基本的快速排序，并在达到一定阈值后切换到插入排序。此实现是算法的原地版本，其执行方式如下：
- 在数组的中间，我们确定一个枢轴，并将其临时交换到末尾。
- 从数组的开头到结尾，我们将任何小于此枢轴的元素交换到开头，与已经移动的其他元素相邻。
- 我们将枢轴交换到这些较小元素旁边。
- 对于枢轴两侧的两个子数组，我们递归地重复此过程。
- 对于小于某个阈值的子数组，插入排序算法接管。
这就是它
/*******************************************************************************
*
* Author: Remi Dufour - remi.dufour@gmail.com
* Date: July 23rd, 2012
*
* Name: Quicksort
*
* Description: This is a well-known sorting algorithm developed by C. A. R.
* Hoare. It is a comparison sort and in this implementation,
* is not a stable sort.
*
* Note: This is public-domain C implementation written from
* scratch. Use it at your own risk.
*
*******************************************************************************/
#include <limits.h>
#include <stddef.h>
/* Insertion sort threshold shift
*
* This macro defines the threshold shift (power of 2) at which the insertion
* sort algorithm replaces the Quicksort. A zero threshold shift disables the
* insertion sort completely.
*
* The value is optimized for Linux and MacOS on the Intel x86 platform.
*/
#ifndef INSERTION_SORT_THRESHOLD_SHIFT
# ifdef __APPLE__ & __MACH__
# define INSERTION_SORT_THRESHOLD_SHIFT 0
# else
# define INSERTION_SORT_THRESHOLD_SHIFT 2
# endif
#endif
/* Macro SWAP
*
* Swaps the elements of two arrays.
*
* The length of the swap is determined by the value of "SIZE". While both
* arrays can't overlap, the case in which both pointers are the same works.
*/
#define SWAP(A,B,SIZE) \
{ \
register char *a_byte = A; \
register char *b_byte = B; \
register const char *a_end = a_byte + SIZE; \
\
while (a_byte < a_end) \
{ \
register const char swap_byte = *b_byte; \
*b_byte++ = *a_byte; \
*a_byte++ = swap_byte; \
} \
}
/* Macro SWAP_NEXT
*
* Swaps the elements of an array with its next value.
*
* The length of the swap is determined by the value of "SIZE". This macro
* must be used at the beginning of a scope and "A" shouldn't be an expression.
*/
#define SWAP_NEXT(A,SIZE) \
register char *a_byte = A; \
register const char *a_end = A + SIZE; \
\
while (a_byte < a_end) \
{ \
register const char swap_byte = *(a_byte + SIZE); \
*(a_byte + SIZE) = *a_byte; \
*a_byte++ = swap_byte; \
}
/* Function Quicksort
*
* This function performs a basic Quicksort. This implementation is the
* in-place version of the algorithm and is done in he following way:
*
* 1. In the middle of the array, we determine a pivot that we temporarily swap
* to the end.
* 2. From the beginning to the end of the array, we swap any elements smaller
* than this pivot to the start, adjacent to other elements that were
* already moved.
* 3. We swap the pivot next to these smaller elements.
* 4. For both sub-arrays on sides of the pivot, we repeat this process
* recursively.
* 5. For a sub-array smaller than a certain threshold, the insertion sort
* algorithm takes over.
*
* As an optimization, rather than performing a real recursion, we keep a
* global stack to track boundaries for each recursion level.
*
* To ensure that at most O(log2 N) space is used, we recurse into the smaller
* partition first. The log2 of the highest unsigned value of an integer type
* is the number of bits needed to store that integer.
*/
void quicksort(void *array,
size_t length,
size_t size,
int(*compare)(const void *, const void *))
{
/* Recursive stacks for array boundaries (both inclusive) */
struct stackframe
{
void *left;
void *right;
} stack[CHAR_BIT * sizeof(void *)];
/* Recursion level */
struct stackframe *recursion = stack;
#if INSERTION_SORT_THRESHOLD_SHIFT != 0
/* Insertion sort threshold */
const int threshold = size << INSERTION_SORT_THRESHOLD_SHIFT;
#endif
/* Assign the first recursion level of the sorting */
recursion->left = array;
recursion->right = (char *)array + size * (length - 1);
do
{
/* Partition the array */
register char *index = recursion->left;
register char *right = recursion->right;
char *left = index;
/* Assigning store to the left */
register char *store = index;
/* Pop the stack */
--recursion;
/* Determine a pivot (in the middle) and move it to the end */
const size_t middle = (right - left) >> 1;
SWAP(left + middle - middle % size,right,size)
/* From left to right */
while (index < right)
{
/* If item is smaller than pivot */
if (compare(right, index) > 0)
{
/* Swap item and store */
SWAP(index,store,size)
/* We increment store */
store += size;
}
index += size;
}
/* Move the pivot to its final place */
SWAP(right,store,size)
/* Performs a recursion to the left */
#define RECURSE_LEFT \
if (left < store - size) \
{ \
(++recursion)->left = left; \
recursion->right = store - size; \
}
/* Performs a recursion to the right */
#define RECURSE_RIGHT \
if (store + size < right) \
{ \
(++recursion)->left = store + size; \
recursion->right = right; \
}
/* Insertion sort inner-loop */
#define INSERTION_SORT_LOOP(LEFT) \
{ \
register char *trail = index - size; \
while (trail >= LEFT && compare(trail, trail + size) > 0) \
{ \
SWAP_NEXT(trail,size) \
trail -= size; \
} \
}
/* Performs insertion sort left of the pivot */
#define INSERTION_SORT_LEFT \
for (index = left + size; index < store; index +=size) \
INSERTION_SORT_LOOP(left)
/* Performs insertion sort right of the pivot */
#define INSERTION_SORT_RIGHT \
for (index = store + (size << 1); index <= right; index +=size) \
INSERTION_SORT_LOOP(store + size)
/* Sorts to the left */
#if INSERTION_SORT_THRESHOLD_SHIFT == 0
# define SORT_LEFT RECURSE_LEFT
#else
# define SORT_LEFT \
if (store - left <= threshold) \
{ \
INSERTION_SORT_LEFT \
} \
else \
{ \
RECURSE_LEFT \
}
#endif
/* Sorts to the right */
#if INSERTION_SORT_THRESHOLD_SHIFT == 0
# define SORT_RIGHT RECURSE_RIGHT
#else
# define SORT_RIGHT \
if (right - store <= threshold) \
{ \
INSERTION_SORT_RIGHT \
} \
else \
{ \
RECURSE_RIGHT \
}
#endif
/* Recurse into the smaller partition first */
if (store - left < right - store)
{
/* Left side is smaller */
SORT_RIGHT
SORT_LEFT
continue;
}
/* Right side is smaller */
SORT_LEFT
SORT_RIGHT
#undef RECURSE_LEFT
#undef RECURSE_RIGHT
#undef INSERTION_SORT_LOOP
#undef INSERTION_SORT_LEFT
#undef INSERTION_SORT_RIGHT
#undef SORT_LEFT
#undef SORT_RIGHT
}
while (recursion >= stack);
}
#undef INSERTION_SORT_THRESHOLD_SHIFT
#undef SWAP
#undef SWAP_NEXT
正如人们所期望的那样，函数原型与C标准中找到的qsort 相同。用于排序整数的比较函数可以与以下相同：
int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
关注点
作为优化，为了不执行实际的递归，我保留了一个全局堆栈来跟踪每个递归级别的边界。
如各种文章所述，整数类型的最高无符号值的log2 是存储该整数所需的位数。因此，保持大小为8 * sizeof(void *) 的堆栈是有意义的。为了确保始终使用不超过O(log2 N)的空间，我首先递归到较小的分区。
根据实验结果，我注意到插入排序在MacOS X上较慢，无论数组大小阈值如何。在尝试保持可移植性的同时，我无法帮助禁用该平台的算法。
历史
- 2012/07/23：首次发布到CodeProject.com
- 2012/07/23：修复了拼写错误、措辞和次要的源代码更改
- 2013/10/13：修复了枢轴计算中的功能问题