该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

  实现两枢轴快速排序算法的核心思想，该算法是Vladimir Yaroslavskiy于2009年提出的对传统快速排序的重要改进，通过使用两个枢轴元素将数组分割为三个部分，显著减少交换操作次数，提高排序效率。

Description

  实现两枢轴快速排序算法，将读入的N个数从小到大排序后输出，并统计排序过程中的比较操作次数和交换操作次数。

算法核心思想

  选择两个枢轴元素P1和P2（其中P1 < P2），将数组划分为三个区域：

• 小于P1的元素区域
• 介于P1和P2之间的元素区域
• 大于P2的元素区域

  然后对这三个区域递归进行排序。

输入格式

  第一行为一个正整数N（1 <= N <= 2 * 10^5）。

  第二行包含N个空格隔开的正整数a_i（1 ≤ a_i ≤ 10^9），为需要进行排序的数。

输出格式

  输出排序后的N个数，用空格分隔。

样例 #1

样例输入 #1

5
2 3 4 1 2

样例输出 #1

1 2 2 3 4
10 3

样例 #2

样例输入 #2

6
8 2 4 9 3 6

样例输出 #2

2 3 4 6 8 9
9 5

算法伪代码

Function DUAL-PIVOT-QUICK-SORT(A, left, right):
    P1 = A[left], P2 = A[right]        // 选择两个轴元素
    if P1 > P2 then
        swap(P1, P2)                   // 确保 P1 ≤ P2
    L = left + 1                       // L 指向小于 P1 区域的右边界
    K = left + 1                       // K 指向当前要处理的元素
    G = right - 1                      // G 指向大于 P2 区域的左边界
    
    while K ≤ G do
        if A[K] < P1 then
            swap(A[K], A[L])
            L++, K++
        else if A[K] > P2 then
            while A[G] > P2 and K < G do
                G = G - 1
            swap(A[K], A[G])
            G = G - 1
            if A[K] < P1 then
                swap(A[K], A[L])
                L = L + 1
            K = K + 1
        else
            K = K + 1                  // P1 ≤ A[K] ≤ P2
    
    swap(A[left], A[L-1])             // 将P1放到正确位置
    swap(A[right], A[G+1])            // 将P2放到正确位置
    
    DUAL-PIVOT-QUICK-SORT(A, left, L-2)
    DUAL-PIVOT-QUICK-SORT(A, L, G)
    DUAL-PIVOT-QUICK-SORT(A, G+2, right)

性能分析

  两枢轴快速排序相比传统单枢轴快速排序的主要优势在于：

• 比较次数：两种算法的平均比较次数都是2nln(n)
• 交换次数：两枢轴快速排序的平均交换次数仅为0.8n\ln(n)，而传统快速排序为1n\ln(n)
• 性能提升：在交换操作上有约20%的性能提升，特别是在处理大型数组时优势更加明显

实验要求

  最后在撰写实验报告时,需要统计本题算法与传统快速排序算法的交换和比较次数,分析在不同规模测试集上的优化效果(测试集可以通过运行实验压缩包里的生成程序lab3/data/generate/gen.cpp获得)