在以下的实现方法中，data包含size个无序元素，并存放在单块连续的存储空间中，快速排序不需要额外的存储空间，所以所有分割过程都在data中完成。当qksort返回时，data就是一个有序的数据集了。
快速排序的关键部分是如何分割数据。这部分工作由函数partition完成。函数分割data中处于i和k之间的元素（i小于k）。
首先，用前面提到的中位数法选取和个分割值。一旦选定分割值，就将k往data的左边移动，直到找到一个小于或等于分割值的元素。这个元素属于左边分区。接下来，将i往右边移动，直到找到一个大于或等于分割值的元素。这个元素属于右边分区。一旦找到的两个元素处于错误的位置，就交换它们的位置。重复这个过程，直到i和k重合。一旦i和k重合，那么所有处于左边的元素将小于等于它，所有处于右边的元素将大于等于它。
qksort中处理递归的过程：在初次调用qksort时，i设置为0，k设置为size-1。首先调用partition将data中处于i和k之间的元素分区。当partition返回时，把j赋于分割点的元素。接下来，递归调用qksort来处理左边的分区(从i到j）。左边的分区继续递归，直到传入qksort的一个分区只包含单个元素。此时i不会比k小，所以递归调用终止。同样，分区的右边也在进行递归处理，处理的区间是从j+1至k。总的来说，以这种递归的方式继续运行，直到首次达到qksort终止的条件，此时，数据就完全排好了。
围绕其平均情况下的性能分析是快速排序的重点，因为一致认为平均情况是它复杂度的度量。虽然在最坏情况下，其运行时间O（n2）并不比插入排序好，但快速排序的性能一般能比较有保障地接近其平均性能O（nlgn），其中n为要排序的元素个数。
快速排序在平均情况下的时间复杂度取决于均匀分布的情况，即数据是否分割为平衡或不平衡的分区。如果使用中位数法，那么此平衡分区将有保障。在这种情况下，当不断分割数组，在图3中用树（高度为（lgn）+1）的方式直观地表示出来。由于顶部为lgn层的树，因此必须遍历所有n个元素，以形成新的分区，这样快速排序的运行时间为O（nlgn）。快速排序不需要额外的存储空间，因此它只使用无序数据本身的存储空间即可。
/*qksort.c*/
#include <stdlib.h>
#include <string.h>
#include "sort.h"
/*compare_int 比较函数*/
static int compare_int(const void *int1, const void *int2)
{
/*对比两个整数的大小（用于中位数分区）*/
if(*(const int *)int1 > *(const int *)int2)
return 1;
else if(*(const int *)int1 < *(const int *)int2)
return -1;
else
return 0;
}
/*partition 分割函数*/
static int partition(void *data, int esize, int i, int k, int (*compare)(const void *key1, const void *key2))
{
char *a=data;
void *pval,
*temp;
int r[3];
/*为分割值和交换值变量分配空间*/
if((pval = malloc(esize)) == NULL)
return -1;
if((temp = malloc(esize)) == NULL)
{
/*如果为交换变量分配空间失败，则将分割变量的空间一起释放掉*/
free(pval);
return -1;
}
/*用中位数法找到分割值*/
r[0] = (rand()%(k-i+1))+i;
r[1] = (rand()%(k-i+1))+i;
r[2] = (rand()%(k-i+1))+i;
/*调用插入排序函数对三个随机数排序*/
issort(r,3,sizeof(int),compare_int);
/*把排好序的三个数的中间值复制给分割值*/
memcpy(pval,&a[r[1]*esize,esize);
/*围绕分割值把数据分割成两个分区*/
/*准备变量范围，使i和k分割超出数组边界*/
i--;
k++;
while(1)
{
/*k向左移动，直到找到一个小于或等于分割值的元素，这个元素处于错误的位置*/
do
{
k--;
}
while(compare(&a[k*esize],pval)>0);
/*i向右移动，直到找到一个大于或等于分割值的元素，这个元素处于错误的位置*/
do
{
i++;
}
while(compare(&a[i*esize],pval)<0);
/*直到i和k重合,跳出分区，否则交换处于错误位置的元素*/
if(i >= k)
{
break;
}
else
{
memcpy(temp, &a[i*esize], esize);
memcpy(&a[i*esize], &a[k*esize], esize);
memcpy(&a[k*esize], temp, esize);
}
}
/*释放动态分配的空间*/
free(pval);
free(temp);
/*返回两个分区中间的分割值*/
return k;
}