哈希排序C++

哈希排序：有序世界的快速构建

在计算机科学中，哈希排序是一种基于哈希表的排序算法。它利用哈希表的特性，将无序数据快速转化为有序状态。本文将通过生动的实例，带你领略哈希排序的魅力。

一、初识哈希排序

想象一下，你有一堆杂乱无章的物品，想要按照某种顺序进行排列。这时，你突然想到一个好主意：给每个物品分配一个独特的编号，然后根据编号快速找到它在有序列表中的位置。这就是哈希排序的核心思想。通过哈希函数将数据映射到哈希表中，我们可以迅速定位并排序数据。

二、实现哈希排序

以下是使用C++实现哈希排序的示例代码：

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

void hashSort(vector<int>& arr) {
    unordered_map<int, pair<int, int>> hashTable;
    for (int i = 0; i < arr.size(); i++) {
        hashTable[arr[i]].first = i; // 记录原始下标
        hashTable[arr[i]].second = arr[i]; // 记录原始值
    }
    for (auto& [key, value] : hashTable) {
        arr[value.first] = key; // 根据原始下标还原排序后的值
    }
}

int main() {
    vector<int> arr = {4, 2, 9, 6, 23, 12, 34, 0, 1};
    hashSort(arr);
    cout << "Sorted array: \n";
    for (int i=0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

在这个示例中，我们使用unordered_map作为哈希表，将数据项作为键，存储其原始下标和值。然后，我们遍历哈希表，根据原始下标还原排序后的值。这样，我们就可以得到一个有序的数组。

三、哈希排序的特点

1. 稳定性：哈希排序是不稳定的排序算法，因为相等的数据项可能会被映射到哈希表的同一位置。
2. 时间复杂度：在最坏的情况下，如果所有数据都映射到同一位置（即哈希冲突），哈希排序的时间复杂度可能达到O(n^2)。但在平均情况下，如果哈希函数分布均匀，时间复杂度可以降低到O(n)。
3. 空间复杂度：哈希排序需要额外的空间来存储哈希表，因此其空间复杂度为O(n)。
4. 适用场景：哈希排序适用于数据量较小或部分有序的情况。对于大规模数据集或高度重复的数据集，选择其他更高效的排序算法可能更为合适。