1 Bubble sort
Each loop compares the size of the two elements before and after, and if the former is greater than the latter, the two are swapped. Doing so replaces the largest element in each loop to the end, gradually forming an ordered collection. The process of gradually moving the largest element in each cycle from the front of the team to the back of the team resembles a “bubbling” process, hence the name.
One way to optimize bubble sorting is to exit the current loop immediately if no swap occurs during a loop because it is already sorted (i.e., time complexity is best)
public int[] bubbleSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
for (int i = 0; i < array.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// Instead of using intermediate variables, use xor to exchange two data
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = true; }}if(! flag) {break; }}return array;
}
Copy the code2 Selection sort
Each loop finds the smallest element in the current loop and swaps it with the first element in the current loop.
public int[] selectSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if(array[j] < array[minIndex]) { minIndex = j; }}if(minIndex > i) { array[i] = array[i] ^ array[minIndex]; array[minIndex] = array[i] ^ array[minIndex]; array[i] = array[i] ^ array[minIndex]; }}return array;
}
Copy the code3 Insert sort
The essence of insert sort is that each time the next element to be sorted is inserted into the previous subset of sorted elements, and each time it determines whether the previous element to be sorted is greater than the element to be sorted. If so, it moves the element to the right, and then determines whether the next element is the same as the element to be sorted… And so on. Compare elements up to less than or equal to where they were inserted. Where we put the equality condition here is important, because that’s what determines whether insertion sort is stable or not.
public int[] insertSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
return array;
}
Copy the code4 Hill sort
Hill sort can be considered an improved version of insertion sort. The array is first divided into groups based on initial increments, each of which uses insert sort internally. Then shrink the increments to regroup, using insert sort again within the group… Repeat the above steps until the increment is 1, at which point the entire array is a group, and the last full insertion sort is done.
The increment at the beginning of the sort is large, and there are more groups, but there is less data in each group, so insert sort is fast. As each round of sorting goes on, the increments and the number of groups become smaller, and the data in each group becomes more and more. However, the sorting is also fast because the array is approaching an ordered state after several rounds of grouping sorting. However, it is not efficient to use insertion sort only for large and unordered data. So in general, hill sort is more efficient than insert sort.
Hill sort execution diagram:
The specific implementation code is as follows:
public int[] shellSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
int gap = array.length >>> 1;
while (gap > 0) {
for (int i = gap; i < array.length; i++) {
int temp = array[i];
int j = i - gap;
while (j >= 0 && array[j] > temp) {
array[j + gap] = array[j];
j = j - gap;
}
array[j + gap] = temp;
}
gap >>>= 1;
}
return array;
}
Copy the code5 heap sort
The process of heap sorting is to build a big top heap, which is a complete binary tree and ensures that the value of a node in the heap is always no greater than that of its parent.
Since the largest element in the big top heap must be the root node, each time the root node is the largest element in the current big top heap, and then the remaining nodes are rebuilt from the big top heap, then the root node is removed, and then rebuilt… This process is repeated until all the data is retrieved, and the final retrieved result is the sorted result.
public class MaxHeap {
/**
* 排序数组
*/
private int[] nodeArray;
/** * The true size of the array */
private int size;
private int parent(int index) {
return (index - 1) > > >1;
}
private int leftChild(int index) {
return (index << 1) + 1;
}
private int rightChild(int index) {
return (index << 1) + 2;
}
private void swap(int i, int j) {
nodeArray[i] = nodeArray[i] ^ nodeArray[j];
nodeArray[j] = nodeArray[i] ^ nodeArray[j];
nodeArray[i] = nodeArray[i] ^ nodeArray[j];
}
private void siftUp(int index) {
// If the value of the node at index is greater than that of its parent, then the two nodes are swapped and index points to its parent
while (index > 0&& nodeArray[index] > nodeArray[parent(index)]) { swap(index, parent(index)); index = parent(index); }}private void siftDown(int index) {
// The index of the left child is smaller than size, which means that the node at index has the left child, indicating that the index node is not a leaf node
while (leftChild(index) < size) {
//maxIndex records the maximum index of the children around the index node
int maxIndex = leftChild(index);
// The index of the right child is less than size, meaning that the index node contains the right child
if (rightChild(index) < size && nodeArray[rightChild(index)] > nodeArray[maxIndex]) {
maxIndex = rightChild(index);
}
// Terminates the loop if the index value is greater than the left and right child values
if (nodeArray[index] >= nodeArray[maxIndex]) {
break;
}
// Otherwise swap, pointing index to the left or right child of the swap, and continue the loop until you reach the leaf nodeswap(index, maxIndex); index = maxIndex; }}private void add(int value) {
nodeArray[size] = value;
size++;
// Build the big top heap
siftUp(size - 1);
}
private void extractMax(a) {
// Swap the top element with the last element
swap(0, size - 1);
// Instead of deleting the elements, we just rebuild the remaining size-1 elements into the big top heap
size--;
// Rebuild the big top heap
siftDown(0);
}
public int[] heapSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
nodeArray = new int[array.length];
for (int value : array) {
add(value);
}
for (int i = 0; i < array.length; i++) {
extractMax();
}
returnnodeArray; }}Copy the codeIn the classic implementation above, if a node needs to be changed, a parent node swap is performed (including the swap between the last node and the first node to be deleted). If you think about it, you’ll see that this is actually redundant. When nodes need to be swapped, only the parent node of the siftUp operation or the child node of the siftDown operation needs to be moved to the current position of the node to be compared, and the comparison node does not need to be moved to their position. At this point, the next judgment will be directly entered, and the siftUp or siftDown process will be repeated until the insertion position of the comparison node is found. The advantage of this is that the operation of node assignment can be saved in half and the execution efficiency can be improved. And that means that you need to store the nodes that you’re comparing as parameters, Exactly in ScheduledThreadPoolExecutor source implementation (” partners who learn source series – ScheduledThreadPoolExecutor (source code line by line with you analysis the author thought) “).
6 merge sort
Merge sort uses the idea of divide-and-conquer. It first splits the array into subarrays of two elements, then sorts and merges the two elements, and recurses upwards. Repeat this recursive process of splitting and merging, and the result is sorted.
The process of merging is to take two Pointers to the first element of two subarrays, compare the two elements, insert the smaller one into a Temp array, move the pointer to the right one bit, and continue comparing the second element of the array with the other element… Repeat the process. Thus, the Temp array holds the result of sorting the two subarrays. Finally, copy the temp array back to its original location.
public int[] mergeSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
return mergeSort(array, 0, array.length - 1);
}
private int[] mergeSort(int[] array, int left, int right) {
if (left < right) {
// The "(left + right) / 2" mode is not selected in order to prevent data overflow
int mid = left + ((right - left) >>> 1);
// Unpack the array
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// Merge subarrays
merge(array, left, mid, right);
}
return array;
}
private void merge(int[] array, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
// P1 and p2 are Pointers to the two arrays to be compared, and k is a pointer to the temp array
int p1 = left, p2 = mid + 1, k = 0;
while (p1 <= mid && p2 <= right) {
if (array[p1] <= array[p2]) {
temp[k++] = array[p1++];
} else{ temp[k++] = array[p2++]; }}// Place the rest of the array directly into the temp array
while (p1 <= mid) {
temp[k++] = array[p1++];
}
while (p2 <= right) {
temp[k++] = array[p2++];
}
// Copy back to the original array
for (int i = 0; i < temp.length; i++) { array[i + left] = temp[i]; }}Copy the code7 Quick Sort
The core of quicksort is to have a reference data temp, usually the first position of the array element. Then you need two Pointers, left and right, to the first and last element of the array.
Start with right, comparing the right position element with the baseline data. If greater than or equal to, the right pointer is moved left to compare the next element; If less than, the left pointer is assigned to the left pointer (the left pointer is stored in temp), and the left pointer is +1. Then the left pointer is compared.
Compare the left position element with the baseline data. If less than or equal to, the left pointer is moved right to compare the next element; If it is greater than, the left pointer is assigned to the right pointer, and the right pointer is -1. Repeat the process.
The comparison is complete until the left and right Pointers are equal. To complete the sorting operation, assign the baseline data stored in Temp to the position pointed to by the current left and right Pointers.
Then we recursively sort the left and right halves of the underlying data. The recursive process is the same as described above, except that instead of the entire array, the range of the array is now either left or right. When the recursive process is complete, the final result is the sorted result.
Quicksort execution diagram:
As mentioned above, the first element is generally taken as the baseline data. However, if the current data is sorted in order from largest to smallest, but now it is sorted in order from smallest to largest, the data is not evenly allocated and the time complexity will degenerate to
Another way to optimize is that complex sorting methods such as quicksort and merge sort are more efficient than selection sort, bubble sort and insert sort in the case of large data, but slower in the case of small data. So we can choose a threshold, in this case 47 (the same as used in the source code). When the amount of data to be sorted is less than 47, insert sort is used. When the amount of data to be sorted is greater than 47, quicksort is used.
private static final int THRESHOLD = 47;
public int[] quickSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
return quickSort(array, 0, array.length - 1);
}
private int[] quickSort(int[] array, int start, int end) {
// If the current amount of data to be sorted is less than or equal to THRESHOLD, insert sort is used; otherwise, quicksort is used
if (end - start <= THRESHOLD - 1) {
return insertSort(array);
}
// The left and right Pointers point to the first and last element of the array, respectively
int left = start, right = end;
/* Take the middle of the left-most, right-most, and middle-most elements as the base data to avoid the case where the first value is taken as the base data every time and the time complexity may degenerate to O(n^2) */
int middleOf3Indexs = middleOf3Indexs(array, start, end);
if(middleOf3Indexs ! = start) { swap(array, middleOf3Indexs, start); }// Temp stores baseline data to be compared in the array
int temp = array[start];
while (left < right) {
If the value of the right pointer is greater than temp, move the right pointer to the left
while (left < right && array[right] >= temp) {
right--;
}
// If the value of the right pointer is less than temp, then the value of the right pointer is assigned to the left pointer
if (left < right) {
array[left] = array[right];
left++;
}
If the left pointer is less than temp, move the left pointer to the right
while (left < right && array[left] <= temp) {
left++;
}
// If the left pointer is greater than temp, assign the left pointer to the right pointer
if(left < right) { array[right] = array[left]; right--; }}// When the left and right Pointers are equal, the loop breaks out and assigns the previously stored baseline data to the same data point as the current two Pointers
array[left] = temp;
// After a substitution, the data to the left of the base data is exchanged recursively
if (start < left - 1) {
array = quickSort(array, start, left - 1);
}
// Then exchange the data to the right of the base data recursively
if (right + 1 < end) {
array = quickSort(array, right + 1, end);
}
return array;
}
private int middleOf3Indexs(int[] array, int start, int end) {
int mid = start + ((end - start) >>> 1);
if (array[start] < array[mid]) {
if (array[mid] < array[end]) {
return mid;
} else {
returnarray[start] < array[end] ? end : start; }}else {
if (array[mid] > array[end]) {
return mid;
} else {
returnarray[start] < array[end] ? start : end; }}}private void swap(int[] array, int i, int j) {
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
Copy the code8 Counting sort
The above seven sorting algorithms are comparison sorting, that is, based on the comparison of elements to sort. The following three sorting algorithms are non-comparison sorting, the first is counting sorting.
Counting sort creates a temporary array of the number of occurrences of each number. For example, if the array to be sorted is [3, 3, 5, 2, 7, 4, 2], the data recorded in the temporary array is [2, 2, 1, 1, 0, 1]. 2 occurs twice, 3 occurs twice, 4 occurs once, 5 occurs once, 6 occurs zero, and 7 occurs once. All you need to do is loop through the count in the temporary array.
public int[] countingSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
// Records the maximum value in the array to be sorted
int max = array[0];
// Records the minimum value in the array to be sorted
int min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if(i < min) { min = i; }}int[] temp = new int[max - min + 1];
// Count the number of occurrences of each number
for (int i : array) {
temp[i - min]++;
}
int index = 0;
for (int i = 0; i < temp.length; i++) {
// When a number is printed, the count of the current position is reduced by one until it reaches zero
while (temp[i]-- > 0) { array[index++] = i + min; }}return array;
}
Copy the codeAs you can see from the above implementation, count sort is only suitable for scenarios with small data spans. If the gap between the maximum and minimum values is large, the resulting temporary array will be longer. Let’s say an array is [2, 1, 3, 1000] with a minimum of 1 and a maximum of 1000. A temporary array of length 1000 would be generated, but most of the space would be useless, so the space complexity would be high.
Counting sort is a stable sorting algorithm, but this is not reflected in the above implementation, which does not maintain order between the same elements. So you need to do some transformation: start with the second element in the temporary array and add the value of the previous element to each element. Take the [3, 3, 5, 2, 7, 4, 2] array as an example. After counting, the temporary array is [2, 2, 1, 1, 0, 1], then perform the above transformation, each number adds the preceding number, the result is [2, 4, 5, 6, 6, 7]. In this case, the temporary array is no longer the number of occurrences of each number, but the position of each number in the last sorted array +1 (if there is a duplicate number, the last one is recorded). For the above sorted array, the last sorted array should be [2, 2, 3, 3, 4, 5, 7]. 1, 3, 4, 5, 6 +1 = 2, 4, 5, 6, 7 +1 = 2, 4, 5, 6, 7 So, if you go through each value in the original array from back to front, subtract the minimum value from it, and find its index in the transformed temporary array, that is, find the position in the last sorted array. Of course, every time the index in the temporary array is found, the number at that position needs to be -1. If the number is repeated later, it will be inserted before the current position. This also shows that traversal must be from back to front to maintain the order between the same numbers.
public int[] stableCountingSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
// Records the maximum value in the array to be sorted
int max = array[0];
// Records the minimum value in the array to be sorted
int min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if(i < min) { min = i; }}int[] temp = new int[max - min + 1];
// Count the number of occurrences of each number
for (int i : array) {
temp[i - min]++;
}
// Convert the temp array to the position where each number should be stored in the last sorted array +1 (if there are duplicates, the last one is recorded)
for (int j = 1; j < temp.length; j++) {
temp[j] += temp[j - 1];
}
int[] sortedArray = new int[array.length];
// This must be traversed from back to front to ensure stability
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[temp[array[i] - min] - 1] = array[i];
temp[array[i] - min]--;
}
return sortedArray;
}
Copy the code9 bucket sort
The difference between the maximum and minimum values of the counting order above will generate a temporary array of how large a number of buckets will be, with only one data inserted into each bucket. If the difference is large, it will waste space. Can I insert multiple data into a bucket? Sure, and that’s the idea of bucket sorting. Bucket sort is similar to hash table. Through certain mapping rules, the elements in the array are mapped to different buckets. Internal sorting is carried out within each bucket, and finally each bucket is output in sequence. The efficiency and stability of bucket sorting depends on the hashing algorithm and the results of internal sorting. Note that this mapping algorithm is not a normal mapping algorithm and requires that all numbers in each bucket be larger than all numbers in the previous bucket. So the final output is a sorted result. For example, the first bucket holds the numbers 1-30, the second bucket holds the numbers 31-60, the third bucket holds the numbers 61-90… And so on. Here is an implementation:
public int[] bucketSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
// Records the maximum value in the array to be sorted
int max = array[0];
// Records the minimum value in the array to be sorted
int min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if(i < min) { min = i; }}// Calculate the number of buckets (can be customized)
int bucketNumber = (max - min) / array.length + 1;
List<Integer>[] buckets = new ArrayList[bucketNumber];
// Calculate the range of storage per bucket (can be customized or not implemented)
int bucketRange = (max - min + 1) / bucketNumber;
for (int value : array) {
// Calculate which bucket to put in (can be customized implementation)
int bucketIndex = (value - min) / (bucketRange + 1);
// Delay initialization
if (buckets[bucketIndex] == null) {
buckets[bucketIndex] = new ArrayList<>();
}
// Put it into the specified bucket
buckets[bucketIndex].add(value);
}
int index = 0;
for (List<Integer> bucket : buckets) {
// To sort each bucket internally, I'm using quicksort, or I can use other sorting algorithms, or I can continue to recursively sort buckets
quickSort(bucket);
if (bucket == null) {
continue;
}
// Write data from non-null buckets back to array arrays in sequence
for(Integer integer : bucket) { array[index++] = integer; }}return array;
}
Copy the code10 Radix Sort
Radix sort does not sort a number by its entirety, but by the digits above each digit. For example, in the first round of sorting, I take all the bits in the array to sort and sort them; In the second round, I get all the tens of digits in the array to be sorted to sort; I get all the hundreds of digits in the array to sort… And so on. Each round of sorting adds the results of all the previous rounds of sorting, and the final result is an ordered sequence.
Radix sort usually sorts all non-negative integers, but there are other ways to get rid of this limitation (such as adding or multiplying a fixed number, restoring the order after the sorting, etc.). Radix sort is similar to bucket sort in that bucket sort is divided by an interval of values, whereas radix sort is divided by the number of bits. Both sorts depend on other sorting algorithms (if you don’t call bucket sorting recursively). The internal sort of each round is implemented by counting sort, because each digit is a small range of numbers ranging from 0 to 9, so counting sort is appropriate.
Radix sort execution diagram:
The specific implementation code is as follows:
public int[] radixSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
// Records the maximum value in the array to be sorted
int max = array[0];
for (int i : array) {
if(i > max) { max = i; }}// Get the maximum number of bits
int maxDigits = 0;
while(max ! =0) {
max /= 10;
maxDigits++;
}
// A temporary array for counting sorts
int[] temp = new int[10];
// Store the result of each round
int[] sortedArray = new int[array.length];
for (int d = 1; d <= maxDigits; d++) {
// The temp array is emptied before each loop begins
replaceArray(temp, null);
// Count the number of occurrences of each number
for (int a : array) {
temp[getNumberFromDigit(a, d)]++;
}
// Convert the temp array to the position where each number should be stored in the last sorted array +1 (if there are duplicates, the last one is recorded)
for (int j = 1; j < temp.length; j++) {
temp[j] += temp[j - 1];
}
// This must be traversed from back to front to ensure stability
for (int i = array.length - 1; i >= 0; i--) {
int index = getNumberFromDigit(array[i], d);
sortedArray[temp[index] - 1] = array[i];
temp[index]--;
}
// After a counting sort, assign the sorted result to the original array
replaceArray(array, sortedArray);
}
return array;
}
private final static int[] sizeTable = {1.10.100.1000.10000.100000.1000000.10000000.100000000.1000000000};
/** * gets the number in the specified number */
private int getNumberFromDigit(int number, int digit) {
if (digit < 0) {
return -1;
}
return (number / sizeTable[digit - 1]) % 10;
}
private void replaceArray(int[] originalArray, int[] replaceArray) {
if (replaceArray == null) {
for (int i = 0; i < originalArray.length; i++) {
originalArray[i] = 0; }}else {
for (int i = 0; i < originalArray.length; i++) { originalArray[i] = replaceArray[i]; }}}Copy the code11 Complexity and stability
| Sorting algorithm | Time complexity | Spatial complexity | The stability of | ||
|---|---|---|---|---|---|
| On average | The best situation | The worst | |||
| Bubble sort | |
|
|
 |
stable |
| Selection sort | |
|
|
|
unstable |
| Insertion sort | |
|
|
|
stable |
| Hill sorting | It depends on the choice of increment | |
unstable | ||
| Heap sort | |
|
|
|
unstable |
| Merge sort | |
|
|
|
stable |
| Quick sort | |
|
|
 |
unstable |
| Count sorting |  |
|
|
 |
stable |
| Bucket sort | It depends on the result of bucket hash and the time complexity of the internal sorting algorithm |  |
stable | ||
| Radix sort |  |
|
|
 |
stable |
(including:
- K represents the difference between the maximum and minimum value in counting sort;
- L indicates the number of buckets in bucket sorting.
- D represents the largest number of digits in radix sort, and r represents the number of bases;
- The time complexity of Hill sort depends largely on the choice of incremental gap sequence, and different deltas have different time complexity. The “gap= Length /2” and “gap=gap/2” used in this paper is a common way, also known as Hill delta, but it is not optimal. In fact, the selection and proof of Hill sort increments has always been a mathematical problem, and the following figure lists most of the gap sequence choices so far.
12 small eggs: monkey sort
In the development of computer science for several decades, many excellent algorithms have been born, and everyone is working hard to develop a more efficient algorithm. But there are also some funny algorithms that are just for fun, and monkey sorting is one of them.
The implementation of monkey sorting is very simple, randomly find two elements to swap, until the random swap to the end of the correct order will not stop.
public int[] bogoSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
Random random = new Random();
while(! inOrder(array)) {for (int i = 0; i < array.length; i++) {
int swapPosition = random.nextInt(i + 1);
if (swapPosition == i) {
continue; } array[i] = array[i] ^ array[swapPosition]; array[swapPosition] = array[i] ^ array[swapPosition]; array[i] = array[i] ^ array[swapPosition]; }}return array;
}
private boolean inOrder(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
return false; }}return true;
}
Copy the codeFor more content, please pay attention to wechat official account: Geek Time
The original is not easy, without permission, please do not reprint, reproduction will be corrected