FilterSort排序算法性能如何？是否优于Quicksort？

void filter_sort(int arr[], int n) {
    if (n <= 1) return;
    if (n == 2) {
        if (arr[0] > arr[1]) {
            int tmp = arr[0]; arr[0] = arr[1]; arr[1] = tmp;
        }
        return;
    }
    if (n == 3) {
        if (arr[0] > arr[1]) { int tmp = arr[0]; arr[0] = arr[1]; arr[1] = tmp; }
        if (arr[1] > arr[2]) { int tmp = arr[1]; arr[1] = arr[2]; arr[2] = tmp; }
        if (arr[0] > arr[1]) { int tmp = arr[0]; arr[0] = arr[1]; arr[1] = tmp; }
        return;
    }

    int i = 0;
    int j = n - 1;
    
    while (i < j) {
        if (arr[i] > arr[j]) {
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
        
        if (i + 1 < j) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp;
            }
            if (arr[j - 1] > arr[j]) {
                int tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp;
            }
        }
        i++;
        j--;
    }

    int mid = n / 2;
    filter_sort(arr, mid);
    filter_sort(arr + mid, n - mid);
}

时间复杂度验证 #

你的算法确实是**O(n log n)**的时间复杂度：

• 每一层递归中，while循环遍历约n/2对元素，每轮操作都是常数时间，单层级时间开销为O(n)
• 递归将数组拆分为两个近似相等的子数组，递归深度为log₂n级别
• 符合分治算法O(n log n)的时间复杂度推导逻辑

实际性能与快排的对比 #

filter_sort很难优于工业级优化的快速排序，核心原因如下：

1. 缓存局部性劣势：快排的分区操作连续访问数组局部区域，CPU缓存命中率高；而你的算法同时从数组两端向中间遍历，频繁跳转首尾位置，缓存利用率低，实际运行速度会受影响。
2. 交换操作冗余：算法仅做首尾或相邻元素的交换，没有像快排那样通过基准值划分元素区间，无法有效减少后续递归的排序工作量，每一层预处理对数组有序性的提升有限。
3. 缺乏基准优化：快排通过三数取中、随机基准等策略避免最坏情况（O(n²)），同时有效划分元素；你的算法无明确基准选择逻辑，虽递归拆分均分，但每一层无法有效分离大小元素，后续递归仍需处理大量无序内容。
4. 成熟快排的额外优化：工业级快排会结合插入排序（处理小数组）、尾递归优化、内联展开等，你的算法仅对n=2、3的小场景做了处理，整体优化程度远不及成熟实现。

总结 #

filter_sort作为分治排序的尝试，思路有新意，但实际性能无法超过优化后的快速排序。如果是学习分治思想的练习，这个实现很有价值；但生产环境中，优先选择标准库中经过充分优化的排序实现（如qsort）。

内容的提问来源于stack exchange，提问作者LaSoupresa