Сортировка, известная ранеесортировка выбором,Пузырьковая сортировка,Сортировка вставками,Сортировка слиянием,быстрая сортировкаВсе они сортируются на основе сравнения, а групповая сортировка предлагает новую идею, то есть сортировку на основе состояния данных.
Сортировка по идее ковшовой сортировки
- сортировка по подсчету
- сортировка по основанию
Особенности сортировки ведром
- Сортировка по идее сортировки ведра не основана на сравнении.
- Временная сложность — O(N), а дополнительная пространственная нагрузка — O(M).
- Область применения ограничена, и состояние данных образца должно соответствовать сегменту ведра.
Требования к классической сортировке по счету и сортировке по основанию для проб
- Вообще говоря, сортировка подсчетом требует, чтобы выборки были целыми числами, а диапазон был относительно узким.
- Вообще говоря, сортировка по основанию требует, чтобы выборки были положительными целыми числами по основанию 10.
Идея сортировки ведром
- Получить диапазон значений неупорядоченного массива
2. «Создать» соответствующее количество «сегментов» в соответствии с диапазоном значений
3. Пройдитесь по массиву и поместите каждый элемент в соответствующее «ведро».
4. Пройдитесь по каждому элементу корзины по порядку и по очереди поместите их в массив, чтобы завершить сортировку массива.
«Корзина» — это контейнер, который может быть реализован с различными структурами данных, включая массивы, очереди или стеки.
сортировка по подсчету
диаграмма
1. Найдите максимальное значение неупорядоченного массива и создайте пустой массив с длиной максимального значения + 1
2. Пройдите по исходному массиву и подсчитайте количество вхождений каждого элемента.
3. Проходим по «ковшу», то есть по массиву, используемому для подсчета количества элементов, и получаем упорядоченный массив
код
public static void countSort(int[] arr){
if (arr == null ||arr.length<2){
return;
}
//找到数组中最大的数
int max = Integer.MIN_VALUE;
for (int i =0;i<arr.length;i++){
max = Math.max(max,arr[i]);
}
//实例化一组桶
int[] bucket = new int[max+1];
//把数组中的数放到自己的桶中
for (int i=0;i<arr.length;i++){
bucket[arr[i]]++;
}
//按照桶的顺序把数倒出来
int i=0;
for (int j=0;j<bucket.length;j++){
while (bucket[j]-->0){
arr[i++]=j;
}
}
}
классическая сортировка по основанию
Принцип состоит в том, чтобы разрезать целое число на разные числа по цифрам, а затем сравнивать каждую цифру отдельно. Изобретение сортировки по основанию можно проследить до вклада Германа Холлери в машину табуляции в 1887 году.
Метод поразрядной сортировки использует сегменты Как следует из названия, при назначении сравниваемых битов (единицы, десять, сотни...) сортируемые элементы распределяются по сегментам 0~9, чтобы достичь эффекта сортировки. В некоторых случаях поразрядная сортировка более эффективна, чем другие сравнительные сортировки.
Шаг алгоритма
- Найдите наибольшее число в данных и определите самый большой бит в отсортированном массиве.
- Унифицируйте все сравниваемые значения (целые положительные числа) до одинаковой длины цифр, а перед числами с более короткими цифрами добавляются нули.
- Сортировать от младшего разряда по порядку
- После сортировки от низшего порядка к высшему последовательность становится упорядоченной последовательностью
анимация
диаграмма
Пример следующего массива
int[] arrays = {6, 4322, 432, 344, 55 };
Теперь у нас есть 10 ведер, каждое из которых может содержать числа array.length.
int[][] buckets = new int[arrays.length][10];
1. Разместите каждую [одну цифру] массива в другом сегменте:
После выделения перерабатываем по порядку: результат должен быть такой: {4322,432,344,55,6}
2. Разместите каждый [десятизначный] массив в другом сегменте (для чисел, подобных 6, добавьте 0 впереди):
После выделения перерабатываем по порядку: результат должен быть таким: {6,4322,432,344,55}
3. Разместите каждую [сотенную цифру] массива в другом сегменте (числа, такие как 6, 55, добавьте 0 впереди):
После выделения перерабатываем по порядку: результат должен быть таким: {6,55,4322,344,432}
4. Разместите каждую [тысячную цифру] массива в другом сегменте (числа, такие как 6, 55, добавьте 0 впереди)
После выделения перерабатываем по порядку: результат должен быть таким: {6,55,344,432,4322}
код
public static int findMax(int[] arrays) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arrays.length; i++) {
max = Math.max(max, arrays[i]);
}
return max;
}
public static void radixSort(int[] arrays) {
int max = findMax(arrays);
//需要遍历的次数由数组最大值的位数来决定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//获取每一位数字(个、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//将其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶
for (int j = 0; j < 10; j++) {
//对每个桶子里的元素进行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(数据初始化会为0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
Обновленная сортировка по основанию
Классическая сортировка по основанию требует дополнительного стека или очереди, но для достижения того же эффекта можно использовать количество вхождений каждой цифры и порядок обхода.
диаграмма
код
public static void radixSortPlus(int[] arr){
if (arr == null ||arr.length<2){
return;
}
radixSortPlus(arr,0,arr.length-1,maxbits(arr));
}
//arr[l..r]排序 , digit 数组中最大的位数
public static void radixSortPlus(int[] arr,int L,int R,int digit){
final int radix = 10;
int i=0;
int j=0;
//有多少个数就准备多少个辅助空间
int[] help = new int[R-L+1];
for (int d=1;d<=digit;d++){ // 最大多少位，就进出多少次
// 10个空间
// count[0] 当前位(d位)是0的数字有多少个
// count[1] 当前位(d位)是(0和1)的数字有多少个
// count[2] 当前位(d位)是(0、1和2)的数字有多少个
// count[i] 当前位(d位)是(0~i)的数字有多少个
int[] count = new int[radix]; // count[0..9]
for (i=L;i<=R;i++){
j = getDigit(arr[i],d);//得到当前位置上的数
count[j]++;
}
//把count 数组变成累加和的形式
for (i=1;i<radix;i++){
count[i] = count[i]+count[i-1];
}
//从右往左遍历
for (i=R;i>=L;i--){
j = getDigit(arr[i],d);
help[count[j]-1] =arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = help[j];
}
}
}
public static int getDigit(int x,int d){
//x /10 的几次方 然后和10 取模，得到该位置上的数
return ((x/((int)Math.pow(10,d-1)))%10);
}
пс: некоторые картинки из интернета, вторглись и удалили.
Сортировать сводку
стабильность
Краткое изложение алгоритмов сортировки
- 1) Сортировка не основана на сравнении, предъявляет строгие требования к выборочным данным и ее нелегко переписать.
- 2) Сортировка на основе сравнения, если указано, как сравнивать размер двух выборок, ее можно повторно использовать напрямую.
- 3) Сортировка на основе сравнения, предел сложности по времени равен O(N*logN)
- 4) Временная сложность O(N*logN), дополнительная пространственная сложность ниже O(N) и не существует стабильной сортировки на основе сравнения.
- 5) Выберите быструю строку для абсолютной скорости, выберите строку кучи для экономии места и выберите слияние для стабильности.