review
We have already described the three most common sorting algorithms:
Java implementation bubble sort explanation
Where is QuickSort?
SelectionSort (Java)
However, the world sort thousands of millions, today the old horse and everyone together to learn the most common several.
Heap sort
Heapsort (English: Heapsort) refers to a sort algorithm designed by using heap data structure.
A heap is a nearly complete binary tree structure that also satisfies the heap property: the child node’s key value or index is always smaller than (or greater than) its parent node.
Basic knowledge of JCIP11 binary heap
The maximum heap
In ascending order, the array is converted to A maxheap, which is A binary tree that satisfies the maxheap Property: A[parent(I)] ≥ A[I] for every node I except the root.
A heap is a complete binary tree with the following properties: the value of each node is greater than or equal to the value of its left and right children, called the big top heap; Or the value of each node is less than or equal to the value of its left and right children, called the small top heap. The diagram below:
Repeatedly take the node with the largest value from the maximum heap (swap the root node with the last node, and move the last node out of the heap) and leave the remaining heap to maintain the maximum heap nature.
At the same time, we number the nodes in the heap by layer, and map this logical structure to an array like this:
Access to heap nodes
Usually the heap is implemented with a onedimensional array.
In the case where the array starts at 0:
The position relation between parent node and child node is as follows:
The index of the left child whose index is I is (2* I +1);
The index of the left child whose index is I is (2* I +2);
The index of the parent whose index is I is floor((i1)/2);
The operation of the heap
In the data structure of the heap, the maximum value in the heap is always at the root node (the minimum value in the heap is at the root node when the heap is used in priority queues).
The following operations are defined in the heap:
Max Heapify: Adjusts the end child of the heap so that the child is always smaller than the parent
Create Build Max Heap: Reorder all the data in the Heap
HeapSort: a recursive operation that removes the root of the first data and makes the maximum heap adjustment
Heapsort algorithm diagram
This diagram comes from heap sort of graphic sorting algorithm (3), and it’s beautifully drawn.
The basic idea
The sequence to be sorted is constructed as a big top heap, in which the maximum value of the entire sequence is the root node at the top of the heap.
Swap it with the trailing element, where the trailing element is the maximum.
The remaining n1 elements are then reconstructed into a heap, which yields the subsmallest values of n elements. Do this repeatedly, and you get an ordered sequence.
steps
Step one constructs the initial heap
The given unordered sequence is constructed into a big top heap (generally the big top heap is used for ascending order and the small top heap is used for descending order).
A. Assume the given unordered sequence structure is as follows
B. At this time, we start from the last nonleaf node (leaf node naturally need not be adjusted, the first nonleaf node arr.length/21=5/21=1, namely the following 6 nodes), and adjust from left to right and from bottom to top.
C. Find the second nonleaf node 4. Since element 9 in [4,9,8] is the largest, 4 and 9 are swapped.
D. At this time, swapping leads to structural disorder of child roots [4,5,6], continue to adjust,6 is the largest in [4,5,6], and swap 4 and 6.
At this point, we construct a large top heap from an unordered sequence.
Step 2 Adjust the heap
Swap the top heap element with the end element to make the end element the largest.
We then continue to adjust the heap, swapping the top element with the bottom element to get the second largest element. And so on and so forth.
A. Swap the top element 9 with the bottom element 4
B. Readjust the structure so that it continues to meet the heap definition
C. Then swap the top element 8 with the bottom element 5 to get the second largest element 8.
The followup process, continue to adjust, exchange, so repeated, eventually making the sequence order
Simple summary
The basic idea of heap sorting is summarized briefly:
A. Build the unnecessary sequence into a heap, and select the big top heap or small top heap according to the ascending and descending requirements;
B. Swap the top element with the end element, and “sink” the largest element to the end of the array;
C. Rearrange the structure so that it meets the heap definition, and then continue swapping the top element with the current end element, repeating the adjust + swap step until the sequence is in order.
Java implementation
instructions
In keeping with the previous logic, we will continue to implement heap sort using list for the time being.
implementation
package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/** * heap sort **@author binbin.hou
* @since0.0.4 * /
public class HeapSort extends AbstractSort {
private static final Log log = LogFactory.getLog(HeapSort.class);
@Override
@SuppressWarnings("all")
protected void doSort(List
original) {
final int maxIndex = original.size()  1;
/* * Step 1: heap the array * beginIndex = first nonleaf node. * Start with the first nonleaf node. You don't need to start at the last leaf node. * A leaf node can be considered a heap compliant node, and the root node is itself and has a maximum value below. * /
int beginIndex = original.size() / 2  1;
for (int i = beginIndex; i >= 0; i) {
maxHeapify(original, i, maxIndex);
}
/* * Step 2: sort heap data * every time, move out the top root node A[0], and switch with the tail node, and traverse length 1. * Then rearrange the last element that has been swapped to the root node to conform to the characteristics of the heap. * Until the unsorted heap length is 0. * /
for (int i = maxIndex; i > 0; i) {
InnerSortUtil.swap(original, 0, i);
maxHeapify(original, 0, i  1); }}/** * adjust the index to index data to match heap characteristics. * *@paramThe list list *@paramIndex Indicates the index of the data to be heaped@paramLen The length of the unsorted heap *@since0.0.4 * /
@SuppressWarnings("all")
private void maxHeapify(final List list, int index, int len) {
int li = (index * 2) + 1; // Index of the left child node
int ri = li + 1; // Index of the right child node
int cMax = li; // Maximum index of child value, default left child.
// The index of the left child node is out of the calculation range.
if (li > len) {
return;
}
// Determine which child node is larger.
if (ri <= len && InnerSortUtil.gt(list, ri, li)) {
cMax = ri;
}
if (InnerSortUtil.gt(list, cMax, index)) {
InnerSortUtil.swap(list, cMax, index); // If the parent node is switched,
maxHeapify(list, cMax, len); // Then you need to continue to determine whether the replaced parent complies with the characteristics of the heap.}}}Copy the code
Insertion sort
Insertion Sort is a simple and intuitive sorting algorithm.
It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.
In the implementation of insertion sort, inplace sort is usually adopted (that is, the sort only needs to use O(1) extra space). Therefore, in the process of scanning from back to front, the sorted elements need to be moved backward step by step repeatedly to provide insertion space for the latest elements.
Algorithm steps
In general, insert sorts are implemented on arrays using inplace. The specific algorithm is described as follows:

Start with the first element, which can be considered sorted

Takes the next element and scans back to front in the sorted element sequence

If the element (sorted) is larger than the new element, move the element to the next position

Repeat step 3 until you find a place where the sorted element is less than or equal to the new element

After inserting the new element into the location

Repeat steps 2 to 5
Java implementation
Java implementation
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/** * bubble sort *@author binbin.hou
* @since0.0.5 * /
@ThreadSafe
public class InsertSort extends AbstractSort {
private static final Log log = LogFactory.getLog(InsertSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
for(int i = 1; i < original.size(); i++) {
Comparable current = (Comparable) original.get(i);
int j = i1;
// Move all information larger than the current element backward by traversing backwards.
while (j >= 0 && InnerSortUtil.gt(original, j, current)) {
// Move the element back one bit
original.set(j+1, original.get(j));
j;
}
// Insert the element into the corresponding position
original.set(j+1, current); }}}Copy the code
Shellsort
Also known as the descending incremental sort algorithm, it is a more efficient and improved version of insertion sort.
Hill sort is an unstable sort algorithm.
Hill sort is an improved method based on the following two properties of insertion sort:

Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort

But insert sort is generally inefficient because it can only move data one bit at a time
Algorithm implementation
Hill sort improves the performance of insert sort by dividing all the compared elements into several regions.
This allows an element to make one big step towards its final position at a time. The algorithm then takes smaller and smaller steps for sorting. The last step of the algorithm is ordinary insert sort, but by this step, the data to be sorted is almost already sorted (insert sort is faster).
Suppose you have a small piece of data at the end of an array sorted in ascending order. If you use a sort of O(n^2) complexity (bubble sort or insert sort), it may take n comparisons and swaps to move the data to the right place.
Hill sort, on the other hand, moves data with larger steps, so small data can get to the right place with only a few comparisons and swaps.
A more understandable implementation of Hill sort is to put array columns in a table and sort the columns (by insertion sort). Repeat the process, but each time with a longer column. You end up with just one column.
Converting an array to a table is to better understand the algorithm, which itself only sorts the original array (by increasing the index’s step size, for example I += step_size instead of I ++).
example
For example, if we have a set of numbers [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10] and start sorting with steps of 5, we can better describe the algorithm by placing the list in a table with five columns, so that they should look like this:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Copy the code
Then we sort each column:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Copy the code
[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]
At this point 10 has moved to the correct position, and then sort by step 3:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
Copy the code
After sorting, it becomes:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
Copy the code
Finally sort by 1 step (this is a simple insertion sort).
How to choose the step size sequence?
Donald Shell initially suggested choosing a step size of n/2 and taking half the step size until it reached 1.
Although this can be better than the O(n^2) algorithm (insertion sort), there is still room to reduce the average and worst times.
The best known sequence of step sizes was proposed by Sedgewick (1, 5, 19, 41, 109…). .
Another sequence of steps that works well in large arrays is the Fibonacci sequence that takes the zeros and ones out of the sequence and computes the remaining numbers to a power twice the golden ratio:
(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713…)
Java code implementation
implementation
For the sake of simplicity, we choose half of the list’s step size and fold it in half.
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/** * hill sort **@author binbin.hou
* @since0.0.6 * /
public class ShellSort extends AbstractSort {
private static final Log log = LogFactory.getLog(ShellSort.class);
@Override
@SuppressWarnings("all")
protected void doSort(List
original) {
// Step size from large to small
for(int step = original.size()/2; step > 0; step /= 2) {
// Insert sort one by one from the first element
for(int i = step; i < original.size(); i++) {
int j = i;
while ((jstep >= 0) && InnerSortUtil.lt(original, j, jstep)) {
// Perform the swap
InnerSortUtil.swap(original, j, jstep);
if(log.isDebugEnabled()) {
log.debug("step: {}, j: {}, jstep: {}, list: {}",
step, j, jstep, original);
}
// Update the step size
j = step;
}
}
}
}
}
Copy the code
The overall implementation is not too difficult, but you can review insertion sort
We have added a log here for your understanding.
Merge sort (English: Merge sort or mergesort)
Is an efficient sorting algorithm created on merge operations, efficiency O(nlogn) (big O symbol). It was first proposed in 1945 by John von Neumann.
This algorithm is a very typical application of Divide and Conquer, and each level of divideandconquer recursion can be performed simultaneously.
An overview of the
Divide and conquer:
Split: To recursively divide the current sequence into equal halves.
Integration: The integration of subsequences from the previous step while preserving the order of the elements (merge).
Java implements recursion
Recursion (topdown)

Apply for a space that is the sum of two sorted sequences and is used to store the combined sequence

Sets two Pointers, starting at the start of two sorted sequences

Compare the elements to which the two Pointers point, place the smaller element into the merge space, and move the pointer to the next position

Repeat step 3 until a pointer reaches the end of the sequence

Copies all remaining elements of the other sequence directly to the end of the merged sequence
Java implementation
In fact, the code is not too difficult to implement, but the recursion is somewhat uncomfortable.
We will explain this later in conjunction with the test log.
package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.ArrayList;
import java.util.List;
/** * merge sort  recursive implementation **@author binbin.hou
* @since0.0.7 * /
public class MergeRecursiveSort extends AbstractSort {
private static final Log log = LogFactory.getLog(MergeRecursiveSort.class);
@Override
@SuppressWarnings("all")
protected void doSort(List
original) {
// store the result of merging
// Fill the array directly to avoid set out of boundsList<? > resultList =new ArrayList<>(original);
sortRecursive(original, resultList, 0, original.size()1);
}
/** * recursive sort *@paramOriginalList originalList *@paramResultList A list of results *@paramStartIx started *@paramEndIx results *@since0.0.7 * /
@SuppressWarnings("all")
private void sortRecursive(List originalList,
List resultList,
int startIx,
int endIx) {
// The loop ends
if(startIx >= endIx) {
return;
}
// Find the middle position and split the list in half
int midIx = (startIx+endIx) / 2;
int leftStart = startIx;
int leftEnd = midIx;
int rightStart = midIx+1;
int rightEnd = endIx;
if(log.isDebugEnabled()) {
log.debug(Ls: {}, le: {}, rs: {}, re: {},
leftStart, leftEnd, rightStart, rightEnd);
}
// recursive call
sortRecursive(originalList, resultList, leftStart, leftEnd);
sortRecursive(originalList, resultList, rightStart, rightEnd);
if(log.isDebugEnabled()) {
log.debug("Operations: ls: {}, le: {}, rs: {}, re: {}",
leftStart, leftEnd, rightStart, rightEnd);
}
// We need to record the starting position through k
int k = startIx;
while (leftStart <= leftEnd && rightStart <= rightEnd) {
// Place the smaller element in the merge space and move the pointer to the next position
Comparable left = (Comparable) originalList.get(leftStart);
Comparable right = (Comparable) originalList.get(rightStart);
// If the left side is smaller, it goes into the merge space
if(left.compareTo(right) < 0) {
resultList.set(k++, left);
leftStart++;
} else{ resultList.set(k++, right); rightStart++; }}// If the list comparison ends, place the remaining elements in the queue.
while (leftStart <= leftEnd) {
resultList.set(k++, originalList.get(leftStart++));
}
while (rightStart <= rightEnd) {
resultList.set(k++, originalList.get(rightStart++));
}
// copy the result to the original collection
for(inti = startIx; i <= endIx; i++) { originalList.set(i, resultList.get(i)); }}}Copy the code
Java iterative implementation
As many of you know, iteration makes code simpler, but complicates debugging and understanding.
Let’s take a look at the implementation of iteration.
Bottomup iterative method
The principle is as follows (assuming a sequence of n elements) :

Merge each two adjacent digits of the sequence to form CEIL (N /2) sequences, and each sequence contains two/one element after sorting

If the number of sequences at this time is not one, the above sequences are merged again to form CEIL (N /4) sequences, and each sequence contains four/three elements

Repeat step 2 until all elements are sorted, that is, the sequence number is 1
Iteration implement
Compared to recursion, this code is much more complicated.
However, this iterative approach has better performance and is implemented as follows.
package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.ArrayList;
import java.util.List;
/** * merge sort  iterative implementation **@author binbin.hou
* @since0.0.7 * /
public class MergeSort extends AbstractSort {
private static final Log log = LogFactory.getLog(MergeSort.class);
@Override
protected void doSort(List
original) {
// store the result of merging
// Fill the array directly to avoid set out of boundsList<? > resultList =new ArrayList<>(original);
// Start, subsequence length 1. Pairwise merge a sequence of length 1
int k = 1;
final int length = original.size();
while (k < length) {
mergePass(original, resultList, k, length);// Merge the previously unordered data into a merge array
k = 2 * k;// Double the subsequence length
mergePass(resultList, original, k, length);// Merge the ordered sequences that have already been merged in pairs back into array original
k = 2 * k;// Double the subsequence length}}/** * merges contiguous sequences of k elements **@paramOriginal Original list *@paramResults Results list *@paramS subsequence length *@paramLen length *@since0.0.7 * /
@SuppressWarnings("all")
private static void mergePass(List original, List results, int s, int len) {
int i = 0;
// Write (I +2*k1 < len) to treat (I +2*k1) as a whole
// From front to back, merge two subsequences of length k into one.
// For the sequence {3, 4, 2, 5, 7, 0, 9, 8, 1, 6}, when k=8, the loop does not enter at all because I >(len2*k+1)
while (i < len  2 * s + 1) {
merge(original, results, i, i + s  1, i + 2 * s  1);// pair merge
i = i + 2 * s;
}
Merge those parts of the "single" merge that are less than two in length with the previous merge.
// Merge (merge is also sort before joining, hence the following merge operation)
if (i < len  s + 1) {
merge(original, results, i, i + s  1, len  1);// merge the last two sequences
} else {
for (int j = i; j < len; j++) {// If there is only one subsequence leftresults.set(j, original.get(j)); }}}/** * Merge two ordered arrays into one ordered array *@paramThe original primitive *@paramResult the results *@paramLow start *@paramMid middle *@paramHigh end *@since0.0.7 * /
@SuppressWarnings("all")
private static void merge(List original, List result, int low, int mid, int high) {
int j, k, l;
// Place records in the temp array from small to large
for (j = mid + 1, k = low; low <= mid && j <= high; k++) {
if (InnerSortUtil.lt(original, low, j)) {
result.set(k, original.get(low++));
} else{ result.set(k, original.get(j++)); }}// The next two loops are to put the remaining number into the temp array
if (low <= mid) {
for (l = 0; l <= mid  low; l++) { result.set(k + l, original.get(low + l)); }}if (j <= high) {
for (l = 0; l <= high  j; l++) { result.set(k + l, original.get(j + l)); }}}}Copy the code
Counting sort Indicates the counting sort
Counting sort is a stable linear time sort algorithm.
The algorithm was proposed by Harold H. Seward in 1954.
The time complexity is reduced to O(N) by counting.
Basic version
Algorithm steps

Find the element with the largest value in the array and call it Max.

Create a new array count, Max plus 1, with elements that default to 0.

Iterate over the elements in the original array, using the elements in the original array as the index of the count array, and the number of occurrences of the elements in the original array as the value of the elements in the count array.

Create the result array result, starting index index.

Each time, the value of the element in count is reduced by 1 until the value of the element is not greater than 0. The remaining elements in count are processed successively.

Returns the result array result.
Java implementation
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/** * count sort **@author binbin.hou
* @since0.0.8 * /
@ThreadSafe
public class CountingSortBasic extends AbstractSort {
private static final Log log = LogFactory.getLog(CountingSortBasic.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
//1. Get the largest element
int max = Integer.MIN_VALUE;
for (Object object : original) {
Integer integer = (Integer) object;
max = Math.max(max, integer);
}
//2. Build the count list
int[] counts = new int[max + 1];
//3. Iterate over the elements in the original array, using the elements in the original array as the index of the count array, and the number of occurrences of the elements in the original array as the value of the elements in the count array.
for (Object object : original) {
Integer integer = (Integer) object;
counts[integer]++;
}
//4. Result construction
int index = 0;
// Iterate over the count array, populating the count array index into the result array
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
// I is actually the value of the element
// Iterate from left to right and the elements will naturally be sorted.
// The same element will appear multiple times, hence the need for a loop.
original.set(index++, i);
counts[i];
if(log.isDebugEnabled()) {
log.debug("Result array: {}", original);
}
}
}
}
}
Copy the code
modified
Waste of space
We’re actually creating an array that’s one more than the largest element, just to fit all the elements.
But it has a defect, that is, there is a waste of space.
{101,109,102,110}, where the maximum value is 110, we need to create a count array with length 111, but we can find that the space in front of it [0,100] is completely wasted, so how to optimize?
Set the array length to maxmin+1, that is, not only find the maximum value, but also find the minimum value, according to the difference between the two to determine the length of the count array.
Improved version implementation
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.Arrays;
import java.util.List;
/** * count sort **@author binbin.hou
* @since0.0.8 * /
@ThreadSafe
public class CountingSort extends AbstractSort {
private static final Log log = LogFactory.getLog(CountingSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
//1. Get the largest and smallest elements
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (Object object : original) {
Integer integer = (Integer) object;
max = Math.max(max, integer);
min = Math.min(min, integer);
}
//2. Build the count list
int[] counts = new int[maxmin + 1];
//3. Iterate over the elements in the original array, using the elements in the original array as the index of the count array, and the number of occurrences of the elements in the original array as the value of the elements in the count array.
for (Object object : original) {
Integer integer = (Integer) object;
// The element is subtracted from the minimum value as the new index
counts[integermin]++;
}
if(log.isDebugEnabled()) {
log.debug("counts.length: {}", counts.length);
}
//4. Result construction
int index = 0;
// Iterate over the count array, populating the count array index into the result array
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
// I is actually the value of the element
// Iterate from left to right and the elements will naturally be sorted.
// The same element will appear multiple times, hence the need for a loop.
// Add the minimum value of the subtraction
original.set(index++, i+min);
counts[i];
if(log.isDebugEnabled()) {
log.debug("Result array: {}", original);
}
}
}
}
}
Copy the code
Own thinking
The nature of the algorithm
What is the nature of this algorithm?
Personal understanding requires only two things:
(1) Each element has its own element position
(2) The same element, the number will increase.
The clever of the algorithm lies in the direct use of the numerical value itself called index, directly skip the sorting comparison; Using technical number, the problem of repeated numerical value is solved.
Inadequacies of algorithms
The trick of this algorithm is also its limitation: you can only compare numbers directly. What if it’s a string?
A little idea
My initial idea was to use a data structure similar to HashMap. This can solve the problem of element filtering, number of statistics.
But it doesn’t solve the sorting problem.
Of course, using TreeMap would be too lame, since it’s already using trees for sorting.
TreeMap version
We use TreeMap here for the following purposes:
(1) Make sorting not limited to numbers.
(2) greatly reduce the waste of memory, not a single element, not a few elements.
The idea is really still the idea of technical ordering.
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/** * Count sort TreeMap **@author binbin.hou
* @since0.0.8 * /
@ThreadSafe
public class CountingSortTreeMap extends AbstractSort {
private static final Log log = LogFactory.getLog(CountingSortTreeMap.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
TreeMap<Comparable, Integer> countMap = new TreeMap<>();
// Initialization times
for (Object object : original) {
Comparable comparable = (Comparable) object;
Integer count = countMap.get(comparable);
if(count == null) {
count = 0;
}
count++;
countMap.put(comparable, count);
}
//4. Result construction
int index = 0;
// Iterate over the count array, populating the count array index into the result array
for (Map.Entry<Comparable, Integer> entry : countMap.entrySet()) {
int count = entry.getValue();
Comparable key = entry.getKey();
while (count > 0) {
// I is actually the value of the element
// Iterate from left to right and the elements will naturally be sorted.
// The same element will appear multiple times, hence the need for a loop.original.set(index++, key); count; }}}}Copy the code
Bucket sort
Or box sort, is a sorting algorithm that works by sorting an array into a finite number of buckets.
Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sort recursively).
Bucket sort is a kind of induction result of pigeon nest sort. Bucket sorting uses linear time O(n) when the values in the array to be sorted are evenly distributed.
Extended version of bucket sort is counting sorting, can count sorting as each barrel only store the same elements, and each barrel storage bucket sort a range of elements, through the mapping function, will be ordered to be mapped to the elements of an array of each corresponding barrels, the elements in each bucket sort, finally will not empty barrels of one element in the original sequence.
In bucket sorting, ensure that the elements are evenly distributed. Otherwise, bucket sorting fails when all data is concentrated in the same bucket.
Algorithm process
Bucket sorting is done with the following procedure:

Set a quantitative array as an empty bucket.

Search the sequence and put the items one by one into the corresponding bucket.

Sort each bucket that is not empty.

Put items back into their original sequence in a bucket that is never empty.
Java implementation
implementation
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/** * Sort buckets **@author binbin.hou
* @since0.0.9 * /
@ThreadSafe
public class BucketSort extends AbstractSort {
private static final Log log = LogFactory.getLog(BucketSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
final int step = 10;
// Calculate the minimum value
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(Object object : original) {
Integer integer = (Integer) object;
min = Math.min(min, integer);
max = Math.max(max, integer);
}
//2. Count the number of buckets
int bucketNum = (maxmin) / step + 1;;
2.1 Initializing the temporary list
List<List<Integer>> tempList = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++) {
tempList.add(new ArrayList<Integer>());
}
//3. Put the elements into the bucket
// There is a restriction: the element must be a left bucket element, smaller than the right bucket element.
// This restricts the comparison to numeric classes, otherwise there is no concept of scope
for(Object o : original) {
Integer integer = (Integer) o;
int index = (integermin) / step;
tempList.get(index).add(integer);
}
// 4. Sort buckets by buckets
// You can choose any algorithm you like
for(int i = 0; i < bucketNum; i++) {
Collections.sort(tempList.get(i));
}
//5. Set results
int index = 0;
for(int i = 0; i < bucketNum; i++) {
List<Integer> integers = tempList.get(i);
for(Integer val : integers) { original.set(index++, val); }}}}Copy the code
Open source address
For your convenience, the above sort has been open source, open source address:
github.com/houbb/sort
Welcome to fork/star and give the author a pat on the back
summary
Hope you found this article helpful, and if you have any other ideas, please share them in the comments section.
All geeks’ likes, favorites and forwarding are the biggest motivation for Lao Ma to continue writing!