目录
【方法】——霍尔数组划分算法——时间复杂度为 O(n)，空间复杂度为 O(1)
一些有趣的事实
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
给定一个数组arr[]，任务是以第一个元素为枢轴元素对数组进行分区。
数组的划分必须满足以下两个条件：
小于枢轴元素的元素必须出现在小于或等于分区索引的索引处。
大于或等于枢轴元素的元素必须出现在大于分区索引的索引处。
分区索引等于元素个数，严格小于枢轴元素个数减一。
注意：可能存在多个分区数组。
例如：
输入： arr[] = [5, 3, 8, 4, 2, 7, 1, 10]
输出： [1, 3, 2, 4 , 8, 7, 5, 10]
说明：分区索引为 3，枢轴元素为 5，所有小于枢轴元素的元素 [1, 3, 2, 4] 排列在分区索引之前，大于或等于枢轴元素的元素 [8, 7, 5, 10] 排列在分区索引之后。
输入： arr[] = [12, 10, 9, 16, 19, 9]
输出： [9, 10, 9 , 16, 19, 12]
说明：分区索引为 2，枢轴元素为 12，所有小于枢轴元素 [9, 10, 9] 的元素都排列在分区索引之前或处，大于或等于枢轴元素 [16, 19, 12] 的元素都排列在分区索引之后。
【方法】——霍尔数组划分算法——时间复杂度为 O(n)，空间复杂度为 O(1)
霍尔分区算法是一种围绕枢轴元素对数组进行高效分区的方法。它基于两个指针，这两个指针分别从数组的两端出发，并向彼此移动，直到找到需要交换的元素。
算法步骤详解：
- 将第一个元素作为枢轴，并初始化两个指针，分别指向数组的开头和结尾。i j
- 向右移动，直到找到大于或等于枢轴的元素；向左移动，直到找到小于或等于枢轴的元素。ij
- 如果指针指向的元素大于或等于枢轴元素，并且指针指向的元素小于或等于枢轴元素，则交换这两个元素。i j
- 重复此过程，彼此移动并靠近，直到相遇或交叉。 i j
- 当指针交叉时，分区完成，小于或等于枢轴的元素在左侧，大于或等于枢轴的元素在右侧。
示例代码：
using System;
class GfG { // Function to partition the array according // to pivot index element static void partition(int[] arr) { int n = arr.Length; int pivot = arr[0]; int i = -1, j = n; while (true) { // find next element larger than pivot // from the left do { i++; } while (arr[i] < pivot); // find next element smaller than pivot // from the right do { j–; } while (arr[j] >= pivot); // if left and right crosses each other // no swapping required if (i > j) break; // swap larger and smaller elements int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
static void Main() { int[] arr = {5, 3, 8, 4, 2, 7, 1, 10}; partition(arr); Console.WriteLine(string.Join(" ", arr)); } }
输出
1 3 2 4 8 7 5 10
一些有趣的事实
霍尔分区算法通常比洛穆托分区算法更快，因为它执行的交换次数更少，并且只对数组进行一次遍历，从而在实践中实现了更好的时间复杂度。
它直接在原地工作，不需要额外的空间，这与使用临时数组的简单分区方法不同。
经过适当的调整，它可以用来实现快速排序的稳定版本，尽管它本身并不稳定。
我们可以通过交换第一个元素和最后一个元素，然后使用相同的代码，轻松地修改算法，将第一个元素（或任何其他元素）视为枢轴。
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
