----- На следующий день -----
————————————
Предположим, что значения 20 случайных целых чисел следующие:
9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9
Как отсортировать эти неупорядоченные случайные целые числа?
Это очень просто, давайте пройдемся по этой неупорядоченной последовательности случайных чисел, каждое целое число будет расставлено в соответствии со своим значением, а соответствующий элемент индекса массива будет увеличен на 1.
Например, если первое целое число равно 9, добавьте 1 к элементу, индекс которого равен 9:
Второе целое число равно 3, затем добавьте 1 к элементу с индексом 3:
Продолжайте обход массива и изменение массива...
Наконец, когда массив пройден, состояние массива выглядит следующим образом:
Значение в каждой позиции нижнего индекса массива представляет собой количество вхождений соответствующего целого числа в последовательности.
С этим «статистическим результатом» сортировка проста. Пройдите массив напрямую, выведите значение нижнего индекса элемента массива, значение элемента несколько раз, и выведите его несколько раз:
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
Очевидно, что эта выходная последовательность уже упорядочена.
public static int[] countSort(int[] array) { //1.得到数列的最大值 int max = array[0]; for(int i=1; i<array.length; i++){ if(array[i] > max){ max = array[i]; } } //2.根据数列最大值确定统计数组的长度 int[] countArray = new int[max+1]; //3.遍历数列，填充统计数组 for(int i=0; i<array.length; i++){ countArray[array[i]]++; } //4.遍历统计数组，输出结果 int index = 0; int[] sortedArray = new int[array.length]; for(int i=0; i<countArray.length; i++){ for(int j=0; j<countArray[i]; j++){ sortedArray[index++] = i; } } return sortedArray;}
public static void main(String[] args) { int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10}; int[] sortedArray = countSort(array); System.out.println(Arrays.toString(sortedArray));}Этот код добавляет шаг в начале, который должен найти максимальное целочисленное значение max последовательности. Длина статистического массива countArray, созданного позже, равна max+1, чтобы гарантировать, что последний индекс массива равен max.
95, 94, 91, 98, 99, 90, 99, 93, 91, 92
Как решить эту проблему?
Очень просто, мы больше не используем (максимальное значение входной последовательности + 1) как длину массива статистики, а (разницу между максимальным и минимальным значениями последовательности + 1) как длину статистики множество.
Между тем, минимальное количество столбцов как смещение для осуждения статистического массива.
Взяв последовательность только что в качестве примера, длина массива статистики составляет 99-90+1 = 10 , а смещение равно минимальному значению последовательности 90 .
Для первого целого числа 95 соответствующий индекс массива статистики равен 95-90 = 5, как показано на рисунке:
Что это обозначает? Давайте посмотрим на следующий пример:
Учитывая таблицу оценок учащегося, необходимо отсортировать оценки от низких к высоким.Если оценки совпадают, соблюдается порядок, присущий исходной таблице.
Затем, когда мы заполняем массив статистики, мы знаем только, что есть два друга с ничьей по 95 очков, но мы не знаем, кто из них Красный, а кто Зеленый:
Следующее объяснение будет немного изматывающим, пожалуйста, сидите спокойно. Мы по-прежнему возьмем в качестве примера таблицу результатов учащихся и преобразуем предыдущий статистический массив в следующий:
Как это деформируется? Массив статистики начинается со второго элемента, и к каждому элементу добавляется сумма всех предыдущих элементов.
Зачем добавлять? Друзья, которые видят это впервые, могут найти это необъяснимым.
Цель этого добавления — сделать значение элемента, хранящегося в массиве статистики, равным конечной отсортированной позиции соответствующего целого числа. Например, значение элемента с нижним индексом 9 равно 5, что представляет целое число 9 исходной последовательности, а окончательная сортировка находится на 5-й позиции.
Далее мы создаем выходной массив sortedArray той же длины, что и входной массив. Затем пройдите по входному массиву сзади наперед:
На первом этапе мы пересекаем маленькую зеленую полосу в последней строке таблицы результатов:
Little Green имеет 95 баллов, мы находим элемент, нижний индекс countArray которого равен 5, а значение равно 4, что означает, что Little Green занимает 4-е место.
В то же время мы вычитаем 1 из значения элемента, индекс которого равен 5 в countArray, от 4 до 3, что означает, что окончательный рейтинг будет 3-м в следующий раз, когда мы столкнемся с результатом 95 очков.
На втором шаге мы проходим по маленькому белому в предпоследней строке таблицы результатов:
Оценка Сяобая — 94. Мы находим элемент, нижний индекс countArray которого равен 4, а значение равно 2, что означает, что оценка Сяобая находится на втором месте.
При этом мы вычитаем 1 из значения элемента, индекс которого у countArray равен 4, из 2 в 1, а это значит, что в следующий раз, когда мы столкнемся со счетом 94 балла (на самом деле мы с ним не сталкивались), окончательный рейтинг будет первым.
На третьем шаге мы проходим по маленькому красному в предпоследней строке таблицы результатов:
Сяохун — 95 баллов, мы находим элемент, нижний индекс countArray которого равен 5, значение равно 3 (изначально 4, минус 1 становится 3), что означает, что оценка Сяохуна занимает третье место.
При этом мы вычитаем 1 из значения элемента, индекс которого равен 5 в countArray, от 3 до 2, а это значит, что в следующий раз мы столкнемся со счетом 95 баллов (на самом деле мы с ним не сталкивались), окончательный рейтинг 2.
Таким образом, маленькие красные и маленькие зеленые, которые также составляют 95 точек, могут быть четко отсортированы, и именно по этой причине порядок подсчета оптимизированной версии принадлежитстабильная сортировка.
Следующий процесс обхода аналогичен и не будет здесь подробно описываться.
public static int[] countSort(int[] array) { //1.得到数列的最大值和最小值，并算出差值d int max = array[0]; int min = array[0]; for(int i=1; i<array.length; i++) { if(array[i] > max) { max = array[i]; } if(array[i] < min) { min = array[i]; } } int d = max - min; //2.创建统计数组并统计对应元素个数 int[] countArray = new int[d+1]; for(int i=0; i<array.length; i++) { countArray[array[i]-min]++; } //3.统计数组做变形，后面的元素等于前面的元素之和 int sum = 0; for(int i=0;i<countArray.length;i++) { sum += countArray[i]; countArray[i] = sum; } //4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组 int[] sortedArray = new int[array.length]; for(int i=array.length-1;i>=0;i--) { sortedArray[countArray[array[i]-min]-1]=array[i]; countArray[array[i]-min]--; } return sortedArray;}public static void main(String[] args) { int[] array = new int[] {95,94,91,98,99,90,99,93,91,92}; int[] sortedArray = countSort(array); System.out.println(Arrays.toString(sortedArray));}1. Когда разрыв между максимальным и минимальным значениями последовательности слишком велик, сортировка подсчетом не применяется.
Например, учитывая 20 случайных целых чисел в диапазоне от 0 до 100 миллионов, если вы используете сортировку подсчетом, вам нужно создать массив длиной 100 миллионов. Не только серьезная трата места, но и повышенная временная сложность.
2. Когда элементы последовательности не являются целыми числами, сортировка подсчетом не применяется.
Если все элементы последовательности являются десятичными, например 25,213 или 0,00000001, соответствующий массив статистики создать невозможно. Это, очевидно, не может считаться отсортированным.
----КОНЕЦ----
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента