When it comes toTen sorting algorithms, the following ten sorting algorithm summary chart is absolutely classic! As long as the learning algorithm will contact this algorithm graph! As for the ten sorting algorithms, the three algorithms with an average time complexity of O(nlogn) are the most concerned: quicksort, merge sort and heap sort:
Bubble sort
Algorithm steps
-
- Compare adjacent elements. If the first one is bigger than the second, swap them both.
-
- Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.
-
- Repeat this step for all elements except the last one.
-
- Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.
Code implementation
public class BubbleSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
for (int i = 1; i < arr.length; i++) {
// Set a flag, if true, to indicate that the loop did not swap, i.e., that the queue is sorted and the sorting is complete.
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false; }}if (flag) {
break; }}returnarr; }}Copy the codeSelection sort
Algorithm steps
-
- First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence
-
- Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.
-
- Repeat the second step until all elements are sorted.
Code implementation
public class SelectionSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// There are N-1 rounds of comparisons
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// The number of comparisons per round N- I
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// Records the index of the smallest element that can be found so farmin = j; }}// Swap the minimum found with the value of the I position
if(i ! = min) {inttmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; }}returnarr; }}Copy the codeInsertion sort
Algorithm steps
-
- Treat the first element of the first to be sorted sequence as an ordered sequence and the second element to the last element as an unsorted sequence.
-
- Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)
Code implementation
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// Select the appropriate place to insert from the element with subscript 1, since there is only one element with subscript 0 and the default is ordered
for (int i = 1; i < arr.length; i++) {
// Record the data to be inserted
int tmp = arr[i];
// Start from the rightmost of the sorted sequence and find the number less than it
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// There is a smaller number, insert
if (j != i) {
arr[j] = tmp;
}
}
returnarr; }}Copy the codeHill sorting
Algorithm steps
-
- Select an incremental sequence T1, T2… , where Ti > tj, tk = 1;
-
- Sort the sequence k times according to the number of incremental sequences k;
-
- In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
Code implementation
public class ShellSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int gap = 1;
while (gap < arr.length/3) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
returnarr; }}Copy the codeLearn about divide and conquer before you learn about quicksort and merge sort: Divide and conquer is an important algorithm in computer science. The literal interpretation is “divide and conquer”, which is to divide a complex problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems… Until the subproblems can be solved directly, the solution of the original problem is the combination of the solutions of the subproblems.
Divide-and-conquer has three steps at each level of recursion:
Decomposition: decompose the original problem into several smaller, independent, and same form of the original problem sub-problems;
Solution: if the subproblem is small and easy to solve, it is solved directly, otherwise, each subproblem is solved recursively.
Merge: Combine solutions of subproblems into solutions of the original problem.
Quick sort
Algorithm steps
-
- Pick an element from the sequence, called pivot;
-
- Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;
-
- Recursively sorts subsequences of elements less than the base value and subsequences of elements greater than the base value;
The bottom case of recursion is if the sequence is of size zero or one, so it’s always sorted. The algorithm always exits, though recursively, because in each iteration it puts at least one element in its last position.
Code implementation
public class QuickSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return quickSort(arr, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
// Set the pivot value
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private void swap(int[] arr, int i, int j) {
inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the codeMerge sort
Algorithm steps
-
- Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;
-
- Set two Pointers, starting at the start of two sorted sequences;
-
- Compare the elements pointed to by the two Pointers, select 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.
Code implementation
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length); }}while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
returnresult; }}Copy the codeHeap sort
Algorithm steps
-
- Build the sequence to be sorted into a heap H[0…… n-1], and select the big top heap or the small top heap according to (ascending descending requirements);
-
- Swap the heap head (maximum) with the heap tail;
-
- Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.
-
- Repeat step 2 until the heap size is 1.
Code implementation
public class HeapSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) { heapify(arr, i, len); }}private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the codeBucket sort
Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. To make bucket sorting efficient, we need to do two things:
- Increase the number of barrels as much as extra space is available
- The mapping function used can evenly distribute the N input data into K buckets
At the same time, the comparison sorting algorithm is very important to the performance of bucket elements.
Code implementation
public class BucketSort implements IArraySort {
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if(value > maxValue) { maxValue = value; }}int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// Allocate data to buckets using mapping functions
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// Sort each bucket, using insert sort
bucket = insertSort.sort(bucket);
for (intvalue : bucket) { arr[arrIndex++] = value; }}return arr;
}
/** * Automatically expand capacity and save data **@param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
returnarr; }}Copy the codeRadix sort
Code implementation
/** ** for negative numbers, see https://code.i-harness.com/zh-CN/q/e98fa9 */
public class RadixSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/** * gets the highest number */
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if(maxValue < value) { maxValue = value; }}return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (longtemp = num; temp ! =0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// In the case of negative numbers, double the number of queues, where [0-9] corresponds to negative numbers and [10-19] corresponds to positive numbers (bucket + 10).
int[][] counter = new int[mod * 2] [0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (intvalue : bucket) { arr[pos++] = value; }}}return arr;
}
/** * Automatically expand capacity and save data **@param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
returnarr; }}Copy the codeCount sorting
- Repeating element
- Have a negative
Code implementation
public class CountingSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}return arr;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if(maxValue < value) { maxValue = value; }}returnmaxValue; }}Copy the codeSummary of ten sorting algorithms
Based on sorting
- A. It is inefficient to push the biggest one to the ceiling in each round. O(n²) — Master swap
- B. Select sort, which is inefficient, but often uses its internal loop to find the maximum and minimum values of the array. Arrays, although inefficient on average, is fast when the sequence is basically ordered, so it also has its own scope. The Arrays utility class got a major change in 1.7
- D. Hill (reduced incremental sorting), is the improvement of interpolation, spatial thinking training is helpful
Divide and conquer method 1. Subproblem resolution 2. Solving subproblem recursively 3
- E. Quicksort is the most common conventional sorting method in the software industry, and its bidirectional pointer scan and partition algorithm are the core, often used to solve similar problems, especially partition algorithm is used to divide elements of different properties, partition->selectK, also used in the famous top problem O(NlgN), But if the pivot element is not the median, especially if every pivot element is on one side of the array interval, the complexity is reduced to N² industrial optimization: three-point median, absolute median, small data volume split by insertion sort quicksort
- F. Merge sort, space for time — inverse logarithmic merge emphasizes the combination of solutions to subproblems
- G. Heap sort, using the binary heap data structure, is to continue to master the tree structure of the hand = insert row + binary search
The above three are all NlgN complexity, of which fast sorting is the best, is the original address does not need to open up auxiliary space; The heap row is also original, but the constant factor is larger and does not have the advantage.
The above 7 are comparison-based sorts, which can be proved to be best NlgN in the case of random order of elements, proved by decision tree
The following three are non-comparison sorts, which in certain cases will be faster than comparison-based sorts:
1. Count sort is the fastest: O(N+k),k=maxOf(sourceArr) The keywords of the sequence are relatively concentrated, and the boundary is known, and the boundary is small
2. Bucket sorting: Sort buckets first, then use other sorting methods to sort the elements in the buckets, and check out the buckets according to their numbers. (allot – collect) To solve the problem you must pay attention to whether the values of the sequence are evenly distributed in the bucket. If it is not uniform, then there will be many more elements in one bucket than in the other, and the order within the bucket will be sorted by comparison. In extreme cases, all elements in one bucket will still degenerate to NlgN
The time complexity is as follows: O(N+C), where C=N(logN-logM), approximately equal to NlgN, where N is the number of elements and M is the number of buckets.
3. Cardinal sort, kN level (k is the largest number of digits) is integer numerical sort inside fast and stable, regardless of the distribution of elements, only open up fixed auxiliary space (10 buckets)
In contrast to bucket sort, radix sort does not require many buckets at a time. And radix sort hardly requires any “comparison” operations, whereas bucket sort requires that multiple data in a bucket be sorted based on comparison operations when there are relatively few buckets. Therefore, in practice, radix sort is better for decimal integers.
Recommendation: algorithm on | dead simple