100MB大对象数组快速排序最佳方案 如何按Fullname排序Home类数组

100MB的对象数组完全可以在内存中完成排序，不需要额外做外排处理，以下是不同场景下的实现方案：

首选方案：使用语言内置排序API（性能最优） #

绝大多数编程语言的内置排序API都做了深度优化（一般采用内省排序，组合了快速排序、插入排序、堆排序的优势），比手写快速排序的综合性能高30%以上，还能避免手写快排的边界错误。

以你给出的C#风格代码为例，实现代码如下：

// StringComparison可按需调整：Ordinal为最高性能的二进制比较，忽略文化规则
// 需要忽略大小写/自然排序可替换为对应的枚举值
Array.Sort(array, (x, y) => string.Compare(x.Fullname, y.Fullname, StringComparison.Ordinal));

如果是Java环境可以调用Arrays.sort(array, Comparator.comparing(Home::getFullname))，其他语言都有对应的原生排序实现，直接调用即可

备选方案：自定义快速排序实现 #

如果业务要求必须自己实现快速排序，需要做以下核心优化，避免出现最坏O(n²)的时间复杂度：

• 基准值（pivot）采用三数取中法选择，避免有序数组场景下性能暴跌
• 子数组长度小于16~20个元素时切换为插入排序，减少递归调用开销
• 字符串比较直接复用语言内置的优化实现，不要手写字符遍历逻辑，内置实现一般都做了SIMD指令优化，性能远高于手写遍历

自定义快排实现代码（C#） #

// 预定义比较器，避免每次排序重复生成委托开销
private static readonly Comparison<Home> _fullNameComparer = (x, y) => 
    string.Compare(x.Fullname, y.Fullname, StringComparison.Ordinal);

public static void QuickSortHomeArray(Home[] array)
{
    if (array == null || array.Length <= 1) return;
    SortInternal(array, 0, array.Length - 1);
}

private static void SortInternal(Home[] array, int left, int right)
{
    // 短子数组用插入排序替代快排
    if (right - left <= 16)
    {
        InsertionSort(array, left, right);
        return;
    }
    int pivotIndex = Partition(array, left, right);
    SortInternal(array, left, pivotIndex - 1);
    SortInternal(array, pivotIndex + 1, right);
}

private static int Partition(Home[] array, int left, int right)
{
    // 三数取中确定基准值位置
    int mid = left + (right - left) / 2;
    if (_fullNameComparer(array[mid], array[left]) < 0) Swap(array, mid, left);
    if (_fullNameComparer(array[right], array[left]) < 0) Swap(array, right, left);
    if (_fullNameComparer(array[right], array[mid]) < 0) Swap(array, right, mid);
    Swap(array, mid, right - 1);
    Home pivot = array[right - 1];
    
    int i = left;
    int j = right - 1;
    while (true)
    {
        while (_fullNameComparer(array[++i], pivot) < 0) ;
        while (_fullNameComparer(array[--j], pivot) > 0) ;
        if (i < j) Swap(array, i, j);
        else break;
    }
    Swap(array, i, right - 1);
    return i;
}

// 小范围插入排序实现
private static void InsertionSort(Home[] array, int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        Home temp = array[i];
        int j = i;
        while (j > left && _fullNameComparer(array[j - 1], temp) > 0)
        {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

private static void Swap(Home[] array, int a, int b)
{
    (array[a], array[b]) = (array[b], array[a]);
}

额外性能优化建议 #

• 如果排序操作非常频繁，可以给Home类预计算Fullname的哈希值，哈希值不同的情况下不需要逐字符比较字符串，能大幅提升比较速度
• 如果数组中存在大量Fullname相同的元素，可以换成三路快排实现，将相等元素单独划为一个区间，减少递归处理的元素数量
• 不要对字符串做任何预处理操作（比如转存为字符数组），内置的字符串比较逻辑已经是最优实现

内容的提问来源于stack exchange，提问作者Авраам Линкольн