使用平凡哈希函数进行排序

在本教程中，我们将学习使用简单的哈希函数进行排序。我们已经熟悉了各种排序算法，如堆排序、冒泡排序和归并排序等。在这里，我们将使用哈希数组对给定的元素数组进行排序。然而，该算法不适用于较大的元素值（不超过 10^6）。该算法指出，我们给出一个包含负数和正数的数组，并要求使用简单哈希函数对数组进行排序。

使用哈希进行排序

以下是使用哈希实现排序算法的步骤。

1. 第一步，我们初始化一个大小为 (max_element) 的哈希数组，我们需要最大值。
2. 我们遍历数组并记录特定元素的出现次数。
3. 第二步之后，我们只需从哈希数组中的 0 迭代到 max_element。
4. 在迭代哈希数组时，如果我们发现任何哈希位置存储的值大于 0，则表示该元素至少在原始元素列表中出现过一次。
5. Hash[i] 存储元素在列表中出现的次数，因此当其 > 0 时，我们会打印这些元素出现的次数。

让我们来理解以下代码。

示例 -

输出

Sorted Arry: [1, 1, 1, 2, 3, 3, 5, 5, 9] 

解释 -

在此程序中，我们使用简单的哈希函数对数组进行排序。我们找到数组中的最大值，然后创建一个哈希表，其桶的数量等于 max_val + 1。 数组中的每个元素都根据其值插入到哈希表中。最后，我们遍历哈希表并重建排序后的数组。

上述代码的时间复杂度为 O(N + K)，其中 N 是输入数组中的元素数量，K 是数组中值的范围（即最大值与最小值之差）。

以下是时间复杂度的细分

1. 查找数组中的最大值：O(N)

查找数组中的最大值过程需要遍历所有元素一次，时间复杂度为 O(N)。

2. 创建哈希表并插入元素：O(N)

在最坏的情况下，如果数组中的所有元素都具有相同的值，它们将被插入到哈希表的同一个桶中。因此，创建哈希表和插入元素的时间复杂度为 O(N)。

3. 遍历哈希表以重建排序后的数组：O(N + K)

在最坏的情况下，如果数组中的所有元素都是唯一的，哈希表将有 K 个桶，每个桶包含一个元素。遍历哈希表并重建排序后的数组需要访问所有 N 个元素加上 K 个桶，时间复杂度为 O(N + K)。

由于 K 代表数组中值的范围，在大多数实际情况下，它通常小于 N。因此，算法的总体时间复杂度由 O(N) 项主导，我们可以将时间复杂度近似为 O(N)。

如何处理负数

如果我们数组中同时包含负数和正数怎么办？使用简单的哈希算法，我们可以有效地处理负数。

要使用基于哈希的方法对数组进行排序，请遵循以下步骤

步骤 1： 创建两个哈希数组，一个用于正数元素，另一个用于负数元素。

步骤 2： 确定数组中的最大值和最小值，以分别设置正数和负数哈希数组的大小。

步骤 3： 从负数哈希数组中的最小值到 0 进行遍历，并按其在数组中出现的顺序打印元素。

步骤 4： 从正数哈希数组中的 0 到最大值进行遍历，并按其在数组中出现的顺序打印元素。

通过使用这种方法，您可以使用基于哈希的技术有效地对数组进行排序。正数和负数哈希数组可确保即使原始输入数组中的顺序不同，元素也能正确排序。

让我们将上述步骤实现为代码 -

示例 -

输出

Original Array: [5, -3, 2, -7, 1, -4, 6, 0, -1, 3]
Sorted Array: -7 -4 -3 -1 0 1 2 3 5 6

解释 -

好的！让我们逐步分析提供的代码并解释每个部分

1. 定义了 hash_based_sort() 函数来实现基于哈希的排序方法。
2. 该函数接受一个参数 arr，代表需要排序的输入数组。
3. 在函数中，我们首先使用 max 和 min 函数分别查找输入数组中的最大值和最小值。这些值将用于设置正数和负数哈希数组的大小。
4. 我们创建了两个数组 - `positive_hash` 和 `negative_hash`。`positive_hash` 数组用零初始化，大小为 `(max_val + 1)`，其中 `max_val` 是输入数组中的最大值。类似地，`negative_hash` 数组用零初始化，大小为 `(abs(min_val) + 1)`，其中 `min_val` 是输入数组中的最小值。请注意，我们使用 `abs(min_val)` 来确保 `negative_hash` 数组的大小为非负值。
5. 接下来，我们遍历输入数组 `arr`，并根据输入数组中元素的值来填充 `positive_hash` 和 `negative_hash` 数组。对于 `arr` 中的每个正数元素，我们将 `positive_hash` 中对应的位置加 1，对于每个负数元素，我们将 `negative_hash` 中对应的位置加 1。
6. 填充哈希数组后，我们继续打印排序后的数组。我们首先通过反向遍历 `negative_hash` 数组（从最大的负数到 1）来按升序打印负数。对于 `negative_hash` 数组中的每个非零计数，我们打印相应的负值并将计数减 1。
7. 接下来，我们通过从 0 到 `max_val` 遍历 `positive_hash` 数组来按升序打印非负数。对于 `positive_hash` 数组中的每个非零计数，我们打印相应的非负值并将计数减 1。
8. 程序完成，并按升序打印排序后的数组，其中负数在前，非负数在后。

时间复杂度

上述代码的时间复杂度为 O (N + K)，其中 N 是输入数组中的元素数量，K 是数组中值的范围（即最大值与最小值之差）。

空间复杂度

上述代码的空间复杂度为 O (N + K)，其中 N 是输入数组中的元素数量，K 是数组中值的范围（即最大值与最小值之差）。