Предыдущий «Code Brother Byte» представил некоторыеКлассический алгоритм сортировки, их временная сложность предпочтительно равна O(nlogn), тогдаКак отсортировать миллионы заказов по сумме?Как вы думаете, можно ли это реализовать в соответствии с сортировкой слиянием и быстрой сортировкой, которые вы изучили раньше? Функцию можно выполнить, но эффективность слишком низкая. Сегодня «Code Brother» позволит вам поиграть с алгоритмом сортировки в особых сценариях и реализовать сортировку с временной сложностью O(n).
Алгоритм, который вам предстоит выучить в «Brother Code», аналогичен «гонкам на суперкарах», которые позволяют достичь высокой скорости в особых сценариях. Быстрый взвод и слияние – это экономичные и практичные автомобили. Сортировка ведрами, сортировка по счету и сортировка по основанию — это гонки спортивных автомобилей на трассе, также известные какЛинейная сортировка.
Слишком поздно объяснять, садись в машину! Сегодня давайте сначала разберемся с ведром.
Ведро Сортировка
Как следует из названия, будет использоваться «ведро», и основная идея заключается в следующем.Разбиваем данные для сортировки на несколько упорядоченных корзин.Данные в каждой корзине сортируются отдельно.После того как все данные в корзинах отсортированы,вынимаются по порядку корзин.Формируемая последовательность упорядочена.
Чтобы быть эффективным в сортировке ведра, нам нужно сделать следующие две вещи:
- Попробуйте увеличить количество ведер, если у вас достаточно свободного места.
- Используемая функция отображения может равномерно распределить входные данные n по k сегментам.
В то же время для сортировки элементов в корзине выбор алгоритма сортировки также имеет решающее значение для производительности.
Основная идея сортировки ведра заключается в следующем:把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并.
Почему временная сложность O(n)? Давайте выясним.
Если нужно отсортировать n фрагментов данных, нам нужно использовать карту функций, чтобы равномерно распределить их по k сегментам, а количество элементов в каждом сегменте равно y = n/k.
Тогда внутреннее использование быстрой сортировки для каждого сегмента, временная сложность составляет O (y * логика), а временная сложность сортировки k сегментов составляет O (k * y * логика), потому что y = n / k. Таким образом, временная сложность всей сортировки ведра составляет O (n * log (n / k)). Когда количество сегментов k близко к количеству данных n, log(n/k) является небольшой константой, а временная сложность сортировки сегментов близка к O(n).
Выглядит так хорошо, может ли он заменить алгоритм сортировки сложности O(nlogn), представленный братьями по коду?
К сожалению, нет. Трасса, по которой может ехать спортивный автомобиль, особенная и не может заменить семейный автомобиль. На самом деле сценарии его применения очень суровы.
- Данные для сортировки легко равномерно делятся на k сегментов, и между сегментами существует естественный порядок размеров. Таким образом, после сортировки данных в каждом сегменте нет необходимости в повторной сортировке.
- Данные равномерно распределяются между каждым бакетом, если бакетов много и мало бакетов. Временная сложность сортировки в корзине не постоянна, в крайних случаях данные разбиваются на одну корзину, что вырождается во временную сложность O(nlogn).
Применимая сцена
Больше подходит для использования во внешней сортировке. Так называемая внешняя сортировка означает, что данные хранятся на внешнем диске.Объем данных относительно велик, а память ограничена, поэтому они не могут быть загружены в память за один раз.
Например, у нас есть 10 ГБ данных заказа, и мы хотим отсортировать их по сумме заказа (при условии, что все суммы являются целыми положительными числами), но наша память ограничена, всего несколько сотен МБ, и нет возможности загрузить 10 ГБ данных. данные в память одновременно. Что мне делать в это время?
Решения
То же самое верно и для сортировки данных заказа 10G в соответствии с суммой заказа.Минимальная сумма заказа составляет 1 юань, а максимальная — 100 000 юаней. Мы делим все заказы на 100 сегментов в зависимости от суммы: в первом сегменте мы храним заказы на сумму от 1 до 1000 юаней, а во втором сегменте — заказы на сумму от 1001 до 2000 юаней и так далее. . Каждое ведро соответствует файлу и нумеруется и именуется в соответствии с размером диапазона сумм (00, 01, 02...99).
В идеале, если сумма заказа равномерно распределена между 10 000 и 100 000, то заказ будет равномерно разделен на 100 файлов, каждый небольшой файл хранит около 100МБ данных заказа, мы можем Файлы последовательно помещаются в память и сортируются быстрой сортировкой. После того, как все файлы отсортированы, нам нужно только прочитать данные заказа в каждом маленьком файле в соответствии с номером файла, от малого к большому, и записать его в файл, затем этот файл хранит данные заказа в соответствии с количеством Данные заказа отсортированы от мала до велика.
Кодовый бой
/**
* 桶排序：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并
*/
public class BucketSort implements LineSort {
private static final QuickSort quickSort = new QuickSort();
@Override
public int[] sort(int[] sourceArray, int bucketSize) {
// 找出最大、最小值
int minValue = sourceArray[0];
int maxValue = sourceArray[1];
for (int value : sourceArray) {
minValue = Math.min(minValue, value);
maxValue = Math.max(maxValue, value);
}
// 桶数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
int[][] buckets = new int[bucketCount][bucketSize];
// 保存每个桶的数组的元素下标，默认值 0
int[] indexArr = new int[bucketCount];
// 将数组中值分配到各个桶里
for (int value : sourceArray) {
int bucketIndex = (value - minValue) / bucketSize;
// 当前桶的数组达到最大值,需要拓容
if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
ensureCapacity(buckets, bucketIndex);
}
// 将数据放到桶中，并且桶对应的数组下标 + 1
buckets[bucketIndex][indexArr[bucketIndex]++] = value;
}
// 对每个桶进行排序，这里使用了快速排序
int k = 0;
for (int i = 0; i < buckets.length; i++) {
if (indexArr[i] == 0) {
continue;
}
// 默认容量是 bucketSize, 要根据实际桶的容量排序，否则不足 bucketSize 的默认值是 0
quickSort.quickSortInternal(buckets[i], 0, indexArr[i] - 1);
for (int j = 0; j < indexArr[i]; j++) {
sourceArray[k++] = buckets[i][j];
}
}
return sourceArray;
}
/**
* 数组扩容,并保存数据
*
* @param buckets
* @param bucketIndex
*/
private void ensureCapacity(int[][] buckets, int bucketIndex) {
int[] tempArr = buckets[bucketIndex];
int[] newArr = new int[tempArr.length * 2];
for (int j = 0; j < tempArr.length; j++) {
newArr[j] = tempArr[j];
}
buckets[bucketIndex] = newArr;
}
}
модульный тест
Генерация одного миллиона данных, диапазон данных [1, 100000]
@DisplayName("线性排序算法测试")
public class LineSortTest {
private static int length = 100;
private int[] array = new int[length];
@BeforeEach
public void beforeEach() {
Random rand = new Random();
for (int i = 0; i < length; i++) {
// 随机生成 [1, 1000000] 的数据
array[i] = rand.nextInt(length) + 1;
}
}
@DisplayName("桶排序")
@Test
public void testBucketSort() {
BucketSort bucketSort = new BucketSort();
// 100 数据，10 个桶
int[] sort = bucketSort.sort(array, 10);
System.out.println(Arrays.toString(sort));
}
}
Суммировать
Как отсортировать 1 миллион пользователей по возрасту? Разве вопрос мышления не очень прост сейчас? Позвольте мне рассказать вам мое решение.
Фактически, сортировка 1 миллиона пользователей по возрасту аналогична сортировке 500 000 кандидатов по оценкам. Мы принимаем диапазон возрастов от минимального 1 года до максимального 120 лет. Мы можем обойти 1 миллион пользователей, разделить их на 120 сегментов в зависимости от возраста, а затем последовательно просмотреть элементы в 120 сегментах. В результате получаются данные для 1 миллиона пользователей, отсортированные по возрасту.
Ответьте «Добавить группу» в фоновом режиме и присоединитесь к техническому сообществу, чтобы учиться вместе.