哈希排序算法详解

def hash_sort(arr):
    """哈希排序算法的Python实现"""
    if not arr:
        return []
    
    # 找到最大值和最小值
    min_val = min(arr)
    max_val = max(arr)
    
    # 计算哈希表大小
    table_size = max_val - min_val + 1
    
    # 创建哈希表
    hash_table = [[] for _ in range(table_size)]
    
    # 将元素放入哈希表
    for num in arr:
        index = num - min_val  # 简单的哈希函数
        hash_table[index].append(num)
    
    # 从哈希表中收集排序结果
    result = []
    for bucket in hash_table:
        if bucket:
            # 如果桶中有多个元素，可以保持稳定排序
            bucket.sort()  # 桶内排序，可以使用其他排序算法
            result.extend(bucket)
    
    return result

# 测试示例
arr = [42, 15, 73, 28, 95, 39, 15, 86]
sorted_arr = hash_sort(arr)
print("排序前:", arr)
print("排序后:", sorted_arr)

function hashSort(arr) {
    // 哈希排序算法的JavaScript实现
    if (!arr || arr.length === 0) {
        return [];
    }
    
    // 找到最大值和最小值
    let minVal = Math.min(...arr);
    let maxVal = Math.max(...arr);
    
    // 计算哈希表大小
    let tableSize = maxVal - minVal + 1;
    
    // 创建哈希表
    let hashTable = new Array(tableSize);
    for (let i = 0; i < tableSize; i++) {
        hashTable[i] = [];
    }
    
    // 将元素放入哈希表
    for (let num of arr) {
        let index = num - minVal;  // 简单的哈希函数
        hashTable[index].push(num);
    }
    
    // 从哈希表中收集排序结果
    let result = [];
    for (let bucket of hashTable) {
        if (bucket.length > 0) {
            // 桶内排序（保持稳定性）
            bucket.sort((a, b) => a - b);
            result.push(...bucket);
        }
    }
    
    return result;
}

// 测试示例
let arr = [42, 15, 73, 28, 95, 39, 15, 86];
let sortedArr = hashSort(arr);
console.log("排序前:", arr);
console.log("排序后:", sortedArr);