使用c++ 实现有重复元素的递归去重排序

在C++中，我们可以使用递归来实现有重复元素的排序去重。这里可以借助一个辅助函数，比如哈希集合`std::unordered_set`来帮助我们去除重复元素。递归通常用于处理分治问题，这里我们可以将数组分割成两部分，处理左侧、右侧，然后合并结果。

以下是一个简单的示例，使用递归和双指针技术来去重并排序：

#include <iostream>
#include <vector>
#include <unordered_set>

// 辅助函数，用于检查某个元素是否已存在于哈希集中
bool is_unique(const std::vector<int>& arr, int start, int end, std::unordered_set<int>& uniqueSet) {
    if (start >= end)
        return true;

    // 如果当前元素不在哈希集中，则添加并继续处理右半部分
    if (!uniqueSet.count(arr[start]))
    {
        uniqueSet.insert(arr[start]);
        return is_unique(arr, start + 1, end, uniqueSet);
    }

    // 否则，移动右指针到下一个位置
    else
    {
        return is_unique(arr, start + 1, end, uniqueSet);
    }
}

// 主函数，进行递归去重并排序
void recursive_sort_and_remove_duplicates(std::vector<int>& arr, int start = 0, int end = -1)
        end = arr.size() - 1;

    // 如果数组只剩一个元素或为空，直接返回
    if (start >= end)
        return;

    // 选择中间元素作为基准
    int pivot_index = start;
    for (int i = start; i < end; ++i) {
        if (arr[i] < arr[pivot_index])
            pivot_index = i;
    }

    // 将基准元素移到正确的位置
    std::swap(arr[pivot_index], arr[end]);

    // 分治处理左右两侧
    recursive_sort_and_remove_duplicates(arr, start, pivot_index - 1);
    recursive_sort_and_remove_duplicates(arr, pivot_index + 1, end);

    // 现在，arr[pivot_index]已经是有序且无重复的最后一个元素，所以只需处理左半边即可
    is_unique(arr, start, pivot_index - 1, std::unordered_set<int>());
}

int main() {
    std::vector<int> arr = {5, 2, 8, 2, 9, 4, 7, 5, 1, 3};
    std::cout << "Original array: ";
    for (const auto& num : arr)
        std::cout << num << " ";

    recursive_sort_and_remove_duplicates(arr);

    std::cout << "\nSorted and deduplicated array: ";
    for (const auto& num : arr)
        std::cout << num << " ";
    
    return 0;
}