快速排序的思路与改进（C 语言描述）

暴风骤雨
• 阅读 1238

本文中的代码适用于对数组元素进行排序（以整型数据为例）。

自定义的方法

在排序方法之前，定义了三个不同的方法，以便于对数组元素进行比较和交换。为了适用于不同的数据类型，这里使用到了 void 指针以及指针类型的转换，也就是 C 语言中范型的概念。如果需要对不同元素类型的数组进行排序，只修改 LessArr() 方法和 Less() 方法即可。

// 比较整型数组中两个元素的大小
int LessArr(void *arr, int i, int j, int size)
{
    return *(int*) (arr + i * size) < *(int*) (arr + j * size);
}

// 比较两个整型元素的大小
int Less(void *x, void *y)
{
    return *(int*) x < *(int*) y;
}

// 交换数组中元素的方法
void Exch(void *arr, int i, int j, int size)
{
    void * temp = malloc(size);
    memcpy(temp, arr + i * size, size);
    memcpy(arr + i * size, arr + j * size, size);
    memcpy(arr + j * size, temp, size);
    free(temp);
}

未改进的快速排序

基本快速排序

基本快速排序的切分方法中，针对于切分的标志元素（这里是数组的首元素），通过自身与数组中其他元素不断交换位置来达到切分目的。

// 基本快速排序的切分方法
int Partation_Basic(void *arr, int lo, int hi, int size)
{
    int v = lo;
    --lo;
    ++hi;
    while (1)
    {
        while (LessArr(arr, v, --hi, size)) if (hi == v) break;
        if (lo >= hi) break;
        Exch(arr, hi, v, size);
        v = hi;
        while (!LessArr(arr, v, ++lo, size)) if (lo == v) break;
        if (lo >= hi) break;
        Exch(arr, lo, v, size);
        v = lo;
    }
    return v;
}

// 基本快速排序的双参方法
void QuickSort_Basic_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Basic(arr, lo, hi, size);
    QuickSort_Basic_Part(arr, lo, k - 1, size);
    QuickSort_Basic_Part(arr, k + 1, hi, size);
}

// 基本快速排序的单参方法
void QuickSort_Basic(void *arr, int len, int size)
{
    QuickSort_Basic_Part(arr, 0, len - 1, size);
}

后交换快速排序

后交换快速排序同样是使用了很多次交换方法，不过对于基本快速排序来说，交换次数明显减少。因为切分的标志元素总是在大循环结束之后进行的，也就是说在前面的交换里，没有将自身加进来，这样就达成了使用更少的交换次数得到同样效果的目的。

// 后交换快速排序的切分方法
int Partation_Smart(void *arr, int lo, int hi, int size)
{
    int i = lo, j = hi + 1;
    void * v = malloc(size);
    memcpy(v, arr + lo * size, size);
    while (1)
    {
        while (!Less(v, arr + (++i) * size)) if (i == hi) break;
        while (!Less(arr + (--j) * size, v)) if (j == lo) break;
        if (i >= j) break;
        Exch(arr, i, j, size);
    }
    Exch(arr, lo, j, size);
    free(v);
    return j;
}

// 后交换快速排序的双参方法
void QuickSort_Smart_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Smart(arr, lo, hi, size);
    QuickSort_Smart_Part(arr, lo, k - 1, size);
    QuickSort_Smart_Part(arr, k + 1, hi, size);
}

// 后交换快速排序的单参方法
void QuickSort_Smart(void *arr, int len, int size)
{
    QuickSort_Smart_Part(arr, 0, len - 1, size);
}

非交换快速排序

非交换快速排序中并没有使用到前面的交换方法，它是通过事先保存切分标志元素的内容，重复进行前后赋值来实现的。

// 非交换快速排序的切分方法
int Partation_Hole(void *arr, int lo, int hi, int size)
{
    void * v = malloc(size);
    memcpy(v, arr + lo * size, size);
    ++hi;
    while (1)
    {
        while (!Less(arr + (--hi) * size, v)) if (lo >= hi) break;
        if (lo >= hi) break;
        memcpy(arr + lo * size, arr + hi * size, size);
        while (!Less(v, arr + (++lo) * size)) if (lo >= hi) break;
        if (lo >= hi) break;
        memcpy(arr + hi * size, arr + lo * size, size);
    }
    memcpy(arr + lo * size, v, size);
    free(v);
    return lo;
}

// 非交换快速排序的双参方法
void QuickSort_Hole_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Hole(arr, lo, hi, size);
    QuickSort_Hole_Part(arr, lo, k - 1, size);
    QuickSort_Hole_Part(arr, k + 1, hi, size);
}

// 非交换快速排序的单参方法
void QuickSort_Hole(void *arr, int len, int size)
{
    QuickSort_Hole_Part(arr, 0, len - 1, size);
}

几种改进的策略

乱序处理

为了确保数组中数据的随机性，我们可以对数组进行乱序处理。或者随机在数组中选取一个元素作为枢轴（pivot）来对数组进行划分。

三取样切分快速排序

三取样切分也就是三位取中的方法，一般是将数组的首、尾以及中间元素的中位数作为切分元素。为了达到更好的切分效果，也可以选择随机在数组中寻找三个元素，用它们的中位数元素作为枢轴（pivot）进行数组元素的切分。这里我选择了将首、尾以及中三个元素进行比较，将中位元素置于首位，再调用之前完成的未改进方法。

// 三取样切分优化（对数组内容进行操作，置中位元素于首位）
void MedianOf_Three(void *arr, int lo, int hi, int size)
{
    int mid = lo + (hi - lo) / 2;
    if (LessArr(arr, lo, mid, size)) Exch(arr, mid, lo, size);
    if (LessArr(arr, hi, mid, size)) Exch(arr, mid, lo, size);
    if (LessArr(arr, hi, lo, size)) Exch(arr, lo, hi, size);
}

// 三取样切分改进
int Partation_Three(void *arr, int lo, int hi, int size)
{
    MedianOf_Three(arr, lo, hi, size);
    return Partation_Smart(arr, lo, hi, size);
}

// 三取样切分优化的双参方法
void QuickSort_Three_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Three(arr, lo, hi, size);
    QuickSort_Three_Part(arr, lo, k - 1, size);
    QuickSort_Three_Part(arr, k + 1, hi, size);
}

// 三取样切分优化的单参方法
void QuickSort_Three(void *arr, int len, int size)
{
    QuickSort_Three_Part(arr, 0, len - 1, size);
}

三向切分快速排序（熵最优的排序）

在实际应用中可能会出现数据重复次数很多的情况，这就具有很大的改进潜力，我们可以将当前实现的线性对数级的性能提高到线性级别。一个简单的思路就是将数组切分为三个部分。

可以参考《算法》中的描述 熵最优的排序 。

// 三向切分快速排序的双参方法
void QuickSort_ThreeWay_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int lt = lo, i = lo + 1, gt = hi;
    void * v = malloc(size);
    memcpy(v, arr + lo * size, size);
    while (i <= gt)
    {
        if (Less(arr + i * size, v)) Exch(arr, lt++, i++, size);
        else if (Less(v, arr + i * size)) Exch(arr, gt--, i, size);
        else ++i;
    }
    QuickSort_ThreeWay_Part(arr, lo, lt - 1, size);
    QuickSort_ThreeWay_Part(arr, gt + 1, hi, size);
}

// 三向切分快速排序的单参方法
void QuickSort_ThreeWay(void *arr, int len, int size)
{
    QuickSort_ThreeWay_Part(arr, 0, len - 1, size);
}

排序方法的调用

int main(int argc, char *argv[])
{
    int arr[] = {3,1,2,6,9,4,-1,-1,-2,11,23,12,18};
    int len;
    GET_ARRAY_LEN(arr, len);
//    QuickSort_Basic(arr, len, sizeof(int));
//    QuickSort_Smart(arr, len, sizeof(int));
//    QuickSort_Hole(arr, len, sizeof(int));
//    QuickSort_Three(arr, len, sizeof(int));
//    QuickSort_ThreeWay(arr, len, sizeof(int));
    
    for (int i = 0; i < len; ++i) printf("%d ", arr[i]);
    printf("\n");
}

完整代码

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

#define GET_ARRAY_LEN(arr,len) { len = (sizeof(arr) / sizeof(arr[0])); }

// 比较整型数组中两个元素的大小
int LessArr(void *arr, int i, int j, int size)
{
    return *(int*) (arr + i * size) < *(int*) (arr + j * size);
}

// 比较两个整型元素的大小
int Less(void *x, void *y)
{
    return *(int*) x < *(int*) y;
}

// 交换数组中元素的方法
void Exch(void *arr, int i, int j, int size)
{
    void * temp = malloc(size);
    memcpy(temp, arr + i * size, size);
    memcpy(arr + i * size, arr + j * size, size);
    memcpy(arr + j * size, temp, size);
    free(temp);
}

/* ----------------------------------------------- */

// 基本快速排序的切分方法
int Partation_Basic(void *arr, int lo, int hi, int size)
{
    int v = lo;
    --lo;
    ++hi;
    while (1)
    {
        while (LessArr(arr, v, --hi, size)) if (hi == v) break;
        if (lo >= hi) break;
        Exch(arr, hi, v, size);
        v = hi;
        while (!LessArr(arr, v, ++lo, size)) if (lo == v) break;
        if (lo >= hi) break;
        Exch(arr, lo, v, size);
        v = lo;
    }
    return v;
}

// 基本快速排序的双参方法
void QuickSort_Basic_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Basic(arr, lo, hi, size);
    QuickSort_Basic_Part(arr, lo, k - 1, size);
    QuickSort_Basic_Part(arr, k + 1, hi, size);
}

// 基本快速排序的单参方法
void QuickSort_Basic(void *arr, int len, int size)
{
    QuickSort_Basic_Part(arr, 0, len - 1, size);
}

/* ----------------------------------------------- */

// 后交换快速排序的切分方法
int Partation_Smart(void *arr, int lo, int hi, int size)
{
    int i = lo, j = hi + 1;
    void * v = malloc(size);
    memcpy(v, arr + lo * size, size);
    while (1)
    {
        while (!Less(v, arr + (++i) * size)) if (i == hi) break;
        while (!Less(arr + (--j) * size, v)) if (j == lo) break;
        if (i >= j) break;
        Exch(arr, i, j, size);
    }
    Exch(arr, lo, j, size);
    free(v);
    return j;
}

// 后交换快速排序的双参方法
void QuickSort_Smart_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Smart(arr, lo, hi, size);
    QuickSort_Smart_Part(arr, lo, k - 1, size);
    QuickSort_Smart_Part(arr, k + 1, hi, size);
}

// 后交换快速排序的单参方法
void QuickSort_Smart(void *arr, int len, int size)
{
    QuickSort_Smart_Part(arr, 0, len - 1, size);
}

/* ----------------------------------------------- */

// 非交换快速排序的切分方法
int Partation_Hole(void *arr, int lo, int hi, int size)
{
    void * v = malloc(size);
    memcpy(v, arr + lo * size, size);
    ++hi;
    while (1)
    {
        while (!Less(arr + (--hi) * size, v)) if (lo >= hi) break;
        if (lo >= hi) break;
        memcpy(arr + lo * size, arr + hi * size, size);
        while (!Less(v, arr + (++lo) * size)) if (lo >= hi) break;
        if (lo >= hi) break;
        memcpy(arr + hi * size, arr + lo * size, size);
    }
    memcpy(arr + lo * size, v, size);
    free(v);
    return lo;
}

// 非交换快速排序的双参方法
void QuickSort_Hole_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Hole(arr, lo, hi, size);
    QuickSort_Hole_Part(arr, lo, k - 1, size);
    QuickSort_Hole_Part(arr, k + 1, hi, size);
}

// 非交换快速排序的单参方法
void QuickSort_Hole(void *arr, int len, int size)
{
    QuickSort_Hole_Part(arr, 0, len - 1, size);
}

/* ----------------------------------------------- */

// 三取样切分优化（对数组内容进行操作，置中位元素于首位）
void MedianOf_Three(void *arr, int lo, int hi, int size)
{
    int mid = lo + (hi - lo) / 2;
    if (LessArr(arr, lo, mid, size)) Exch(arr, mid, lo, size);
    if (LessArr(arr, hi, mid, size)) Exch(arr, mid, lo, size);
    if (LessArr(arr, hi, lo, size)) Exch(arr, lo, hi, size);
}

// 三取样切分改进
int Partation_Three(void *arr, int lo, int hi, int size)
{
    MedianOf_Three(arr, lo, hi, size);
    return Partation_Smart(arr, lo, hi, size);
}

// 三取样切分优化的双参方法
void QuickSort_Three_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int k = Partation_Three(arr, lo, hi, size);
    QuickSort_Three_Part(arr, lo, k - 1, size);
    QuickSort_Three_Part(arr, k + 1, hi, size);
}

// 三取样切分优化的单参方法
void QuickSort_Three(void *arr, int len, int size)
{
    QuickSort_Three_Part(arr, 0, len - 1, size);
}

/* ----------------------------------------------- */

// 三向切分快速排序的双参方法
void QuickSort_ThreeWay_Part(void *arr, int lo, int hi, int size)
{
    if (lo >= hi) return;
    int lt = lo, i = lo + 1, gt = hi;
    void * v = malloc(size);
    memcpy(v, arr + lo * size, size);
    while (i <= gt)
    {
        if (Less(arr + i * size, v)) Exch(arr, lt++, i++, size);
        else if (Less(v, arr + i * size)) Exch(arr, gt--, i, size);
        else ++i;
    }
    QuickSort_ThreeWay_Part(arr, lo, lt - 1, size);
    QuickSort_ThreeWay_Part(arr, gt + 1, hi, size);
}

// 三向切分快速排序的单参方法
void QuickSort_ThreeWay(void *arr, int len, int size)
{
    QuickSort_ThreeWay_Part(arr, 0, len - 1, size);
}

/* ----------------------------------------------- */

int main(int argc, char *argv[])
{
    int arr[] = {3,1,2,6,9,4,-1,-1,-2,11,23,12,18};
    int len;
    GET_ARRAY_LEN(arr, len);
//    QuickSort_Basic(arr, len, sizeof(int));
//    QuickSort_Smart(arr, len, sizeof(int));
//    QuickSort_Hole(arr, len, sizeof(int));
//    QuickSort_Three(arr, len, sizeof(int));
//    QuickSort_ThreeWay(arr, len, sizeof(int));
    
    for (int i = 0; i < len; ++i) printf("%d ", arr[i]);
    printf("\n");
}
算法
点赞
收藏
评论区
推荐文章
好买-葡萄 好买-葡萄
•
3年前
【数据结构与算法】—— 二分查找
1.二分查找的概念二分查找指的是在排好序的数组中，找到目标元素。如果元素存在则返回元素的下标，不存在则返回1.下面以升序为例进行简单描述2.查找过程：取数组中间元素与查找元素target比较。如果target等于中间元素则直接返回中间元素的下标，如果target小于数组中间元素则在数组左边查找，如果target大于数组中间元素则在右边查找。重复以上步骤。
1028
0
0
似梦清欢 似梦清欢
•
2年前
排序算法（冒泡、快速、插入）
稳定性：排序前后相等的元素位置是否会被交换。冒泡排序strcpy只能拷贝字符串，整型或浮点型数组需要用memcpy。memcpy称为内存拷贝接口，可以将某一段连续的内存放入另一段连续的内存中。在使用随机数的代码中使用固定的数组有利于调试。:::tipmem
1104
0
0
Easter79 Easter79
•
3年前
swift闭包表达式和尾随闭包
我们从一个Swift函数说起。并以此为例子。Swift的标准库提供了一个叫做sorted(by:)的方法，会根据你提供的排序闭包将已知类型的数组的值进行排序。一旦它排序完成，sorted(by:)方法会返回与原数组类型大小完全相同的一个新数组，该数组的元素是已排序好的。原始数组不会被sorted(by:)方法修改。我们以soted方法为例子
1062
0
0
似梦清欢 似梦清欢
•
2年前
排序算法（简单选择、堆排序、归并）
简单选择排序:::tip简单选择排序原理：将未排序的数组中从前向后遍历，找到最小的元素和数组中第一个元素交换位置，此时数组中第一个元素位置已经确定，再将未排序的数组中从前向后遍历，找到最小的元素和数组中第二个元素交换位置，依次向下。:::需要两层循环，外层
981
0
0
Wesley13 Wesley13
•
3年前
java.lang.Comparable
Comparable接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的_自然排序_，类的compareTo方法被称为它的_自然比较方法_。实现此接口的对象列表（和数组）可以通过Collections.sort（和Arrays.sort）进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。
582
0
0
Wesley13 Wesley13
•
3年前
Java面试总结（排序算法）
1.冒泡排序算法描述：两两比较，大的放后面2.选择排序算法描述：在m元数组中找到最小值的位置，然后将最小值的位置和第n(n0,1,2,....m1)位的值对调，排序k次则m元数组中前k(k<m)位的值已经排序好，m元数组中前k位的值不需要再进行排序，此时需要排序的元素只有mk个3.插入排序算
845
0
0
Wesley13 Wesley13
•
3年前
PHP快速排序（原地切分）
        快速排序是一种分治的排序算法，采用递归的思想，将数组元素分为两部分，选择切分元素，左右扫描数组，将大于切分元素的数据放在右边，小于切分元素的数据放在左边，直到扫描指针相遇，切分结束，同时递归调用，直到数组有序。      代码如下：<?phpfunctionquick_sort(array&$array,$l
799
0
0
Stella981 Stella981
•
3年前
C#.NET 对HashTable数组进行按值排序
C.NET对HashTable数组进行按值排序　　最近做了一个项目，需要对一个2维数组的值进行排序然后再取出对应的Key值。开始是用HashTable做的，不过HashTable中的排序只是对Key进行排序，如果想对值进行排序得用其它办法。下面我就把这种方法说下：一.我们先假设一个二维数组，用HashTab
781
0
0
Stella981 Stella981
•
3年前
Lua 排序算法
冒泡排序（BubbleSort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。算法步骤1.有一个长度为n
767
0
0
小万哥 小万哥
•
1年前
NumPy 数组排序、过滤与随机数生成详解
NumPy数组排序排序数组排序数组意味着将元素按特定顺序排列。顺序可以是数字大小、字母顺序、升序或降序等。NumPy的ndarray对象提供了一个名为sort()的函数，用于对数组进行排序。示例：pythonimportnumpyasnparrnp.arr
445
0
0
深度学习 深度学习
•
1星期前
LeetCode 2576题解：双指针法求解最多标记下标（排序+贪心策略）
一、题目解读2576题要求在一个整数中寻找最多可标记的下标对：若nums法”的组合思路：1.排序预处理：对原数组nums进行升序排序，确保相同元素聚集，便于后续配对。2.双划分：将排序后的数组分为左右两半（左指针left0，右指针rightn/2），从
57
0
0
暴风骤雨
暴风骤雨
Lv1
明月却多情，随人处处行。
文章
10
粉丝
0
获赞
0
热门文章
关于Could not set parameters for mapping的问题记录
MaxCompute问答整理之2020-03月
Kubernetes上的蓝/绿部署
国产RPA首登Gartner竞争格局报告，你更需要关注中国RPA市场
Guava自加载缓存LoadingCache使用指南