Top ten classic sorting algorithm animation and analysis, look at me enough! (Complete version with code)
Exchange sort
Bubble sort
The corresponding code
void sort(a) {
// Optimization of pruning
// Based on principle:
// A maximum or minimum value is placed for each complete loop
// Each trip can remove branches and leaves, i.e., the maximum or minimum value
// The size of I also determines the number of values that have been sorted
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array[j], array[j+1]); }}}}Copy the codePrinciple and realization method
In fact, bubble sort, one of the simplest sorting methods, is based on the concept of swapping in pairs, with the highest value placed at the top and the lowest value placed at the bottom.
And the double cycle of violence is how he does it. Each time, the largest digit is placed in the last digit, or vice versa, the smallest digit is placed in the first digit.
Quick sort
The corresponding code
static void sort(int left, int right) {
if (left < right) {
// We have split the left and right sides of the line, the left side must be smaller than the middle line, the right side must be larger than the middle line
int mid = split(left, right);
// Divide the left and right partitions with a center line
sort(mid+1, right);
sort(left, mid-1); }}static int split(int left, int right) {
// Use the first value of the current range array as the center line
int temp = array[left];
while(left < right){
// If the right pointer has a number smaller than the center line, it swaps with the center line
while(left < right && temp < array[right]) right--;
array[left] = array[right];
// If the left pointer has a number larger than the center line, it swaps with the center line
while(left < right && temp > array[left]) left++;
array[right] = array[left];
}
// Left == right, it doesn't matter who does the swap
array[left] = temp;
return left;
}
Copy the codePrinciple and realization method
Quicksort is actually an upgraded version of bubble sort, again based on pairwise swapping, but with the idea of divide-and-conquer. Through the use of the center line, on the need to sorting interval to a partition, and the rest of the internal performance and on the other hand is lies in the center line, because the numerical comparison is no longer a global, local, but for efficiency calculation generally to be O (nlogn), of course, extreme may degenerate back our bubble sort.
Extreme examples: 5 -> 4 -> 3 -> 2 -> 1
If you want to sort an array that’s already sorted, and then you want to sort an array, you’re going to have a degradation of quicksort. The solution is to stop using the first number as the baseline for the midline.
Insertion sort
Direct insertion sort
The corresponding code
void sort(a) {
// The method of building branches and leaves can be used, but the effect is negligible
// Because this is just a calculation based on mathematical methods, it can be known that when variable I =0, there is no need to work, which means that a small part of the work is deleted
for (int i = 1; i < array.length; i++) {
int j = i;
int temp = array[i];
// If the subscript value in the currently sorted array is greater than the current value
// Move the value back
while (j > 0 && temp < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
if (j != i) array[j] = temp;
}
}
Copy the codePrinciple and realization method
Insertion sort, as the name suggests, is about putting numbers in place. The idea is to split an array into two parts, one ordered and one unordered. The ordered queue is formed by constantly deleting values from the unnecessary queue and placing them in the ordered queue.
First order :(5) -> 3 -> 4 -> 7 -> 2 second order :(3 -> 5) -> 4 -> 7 -> 2 third order :(3 -> 4 -> 5) -> 7 -> 2... And so onCopy the codeHill sorting
The corresponding code
static void sort(a) {
// Gap is a group
for (int gap = array.length >> 1; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int j = i;
while (j - gap >= 0&& array[j] < array[j - gap]) { swap(array[j], array[j - gap]); j -= gap; }}}}Copy the codePrinciple and realization method
(2) array[J] : the sequence to be swapped on the right side (3) array[J-GAP] : the sequence to be swapped on the left side (4) j -= gap: is to ensure that the last forgotten data is processed.
The original sequence: 4 - > 5 - > 3 - > 2 - > 1 first process: (2) - > 3 - > 1 (4) - > 5 - > 1 first process 2:2 - > (3) - > 4 - > 3 (5) - > 1 first process: (1) -> 3 -> (2) -> 5 -> (4)Copy the codeSelection sort
Simple selection sort
The corresponding code
void sort(a) {
// Optimization of pruning
// Based on principle: exactly the same as bubble sort.
for (int i = 0; i < array.length; i++) {
// Is used to indicate the minimum subscript
int min = i;
// Loop to find the minimum value
for (int j = i+1; j < array.length ; j++) {
if(array[j] < array[min]) min = j; } swap(array[min], array[i]); }}Copy the codePrinciple and realization method
Sort, which is as simple as bubble sort, is based on the concept of finding the smallest value inside the maintained array and placing it first in the corresponding range.
The solution is also a double cycle of violence.
Heap sort
The corresponding code
static void sort(a){
int len = arr.length;
// Build the big top heap
for (int i = (arr.length - 1) / 2; i >= 0; i--)
heapSort(i, arr.length - 1);
for (int i = arr.length - 1; i > 0; i--) {
// Swap the 0 bit, and put the maximum value at the end
swap(0, i);
// Len minus 1 ensures that the last digit is not processed
// Sort the reciprocal of large numbers
len--;
heapSort(0, len); }}static void heapSort(int i, int len) {
if (i > len) return;
int maxIdx = i;
int firPosition = i * 2 + 1;
int secPosition = i * 2 + 2;
// The left side is large
if (firPosition < len && arr[firPosition] > arr[maxIdx]) maxIdx = firPosition;
if (secPosition < len && arr[secPosition] > arr[maxIdx]) maxIdx = secPosition;
if (maxIdx != i) {
swap(maxIdx, i);
heapSort(maxIdx, len);
}
}
Copy the codePrinciple and realization method
Heap sort, which you can also think of as a tree sort, doesn’t convert this array into a tree, but it’s based on the idea of a tree.
(1) the big top pile of ascending (array) : arr [I] > = arr [2 + 1] I && arr [I] > = arr [2 + 2] I
(2) Small top heap: ARR [I] <= ARr [2i+1] &&arr [I] <= ARr [2i+2]
The conclusion is tree, and traversal mode is a hierarchical traversal comparison:
Original sequence: 4 -> 3 -> 2 -> 5 -> 1 Build the big top heap, a copy of the tree corresponding to the array: 4 2 no subtree 4 5 maxId change 5 / \ no processing. / \ \ / processing / \ 3 4 2 2 = = = = = = > 5 2 = = = > > 4 4 2/3 / \ \ processing treatment 4 / \ \ 5 3 1 3 3 1Copy the codeWe find that once a value change occurs, it is necessary to make an initial corresponding change to the subtree, but why does this step just finish building the tree? Because she doesn’t compare the size of the left and right subtrees, the only thing she can guarantee is that one node is bigger than the left and right subtrees, and she can determine the value of the bottom node. So that brings us to the second step which is actually sorting.
5 -> 4 -> 2 -> 3 -> 1 After the swap: 5 swaps 1 / \ 0 and 4 bits / \ back to the tree above to create 4 2 ===> 4 2 ===> / \ / only remove 4 bits 3, 1, 3, 5Copy the codeMerge sort
The corresponding code
static void sort(int L, int R) {
if(L == R) {
return;
}
int mid = ((L + R) >> 1);
// Continuously split the array directly in half
// Recursively call the regression order
// Merge the left half and the right half
// Merge two arrays
sort(L, mid);
sort(mid + 1, R);
merge(L, mid, R);
}
static void merge(int L, int mid, int R) {
int[] temp = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
// Compare the left and right elements, which is smaller, and fill that element in temp
while(p1 <= mid && p2 <= R) {
temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
// After the above loop exits, fill the remaining elements into temp
while(p1 <= mid) {
temp[i++] = array[p1++];
}
while(p2 <= R) {
temp[i++] = array[p2++];
}
// Copy the final sorting result to the original array
for(i = 0; i < temp.length; i++) { array[L + i] = temp[i]; }}Copy the codePrinciple and realization method
You can already see that merge sort is the opposite of quicksort, because quicksort actually splits the array in half and then merges it.
Breaking it up is easy, but merging is really messy. If there are only two comparisons, then you just say a > B, and swap(a, b). But what about the comparison of two arrays?
The original sequence:4 -> 3 -> 2 -> 5 -> 1The comparison required for the regression of the left half of the sequence, which is calculated to be the first time the two arrays are combined, is:4 -> 3This time the specific merge(0.0.1); The way to merge is to create a new array space to hold it. (1) two arrays {[4], [3}, which will stuff the smaller arrays into the new array temp.while(p1 <= mid && p2 <= R) { temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++]; } (2) The following autoadd strategy is to dump all data into temp at once. A closer look reveals that only the array [3], breaks out of the loop.while(p1 <= mid) {
temp[i++] = array[p1++];
}
while(p2 <= R) {
temp[i++] = array[p2++];
}
Copy the codeCount sorting
The corresponding code
public class countSort {
/** * Min = a [1],Max = a [0] **@param array
* @return* /
private static int[] getMinAndMaxValue(int array[]) {
int[] a = new int[2];
a[0] = a[1] = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > a[0]) a[0] = array[i];
if (array[i] < a[1]) a[1] = array[i];
}
return a;
}
/** * Build an array based on Max and Min, then sort *@param array
* @param max
* @param min
* @return* /
private static int[] countSort(int[] array, int max, int min) {
int[] temp = new int[max - min + 1];
int[] results = new int[array.length];
for (int i = 0; i < array.length; i++) {
temp[array[i] - min]++;
}
int index = 0;
for (int i = 0; i < temp.length; i++) {
while (temp[i] > 0) { results[index++] = i + min; temp[i]--; }}returnresults; }}Copy the codePrinciple and realization method
We can see the use of three loops, one of which is for tuning, which is to find our maximum and minimum.
As can be seen from the figure, counting sort is a process of placing all values in the corresponding index and then rearranging them. So you have this extreme situation.
Extreme cases: [1,999]
Such two data, in time with our tuning, would end up with a temporary array size of 998. If the gap is larger, more space would be wasted. So we’re going to introduce another sort scheme, which is called bucket sort.
Bucket sort
The corresponding code
public class BucketSort {
/** * Min = a [1],Max = a [0] **@param array
* @return* /
private static int[] getMinAndMaxValue(int array[]) {
int[] a = new int[2];
a[0] = a[1] = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > a[0]) a[0] = array[i];
if (array[i] < a[1]) a[1] = array[i];
}
return a;
}
public static ArrayList<ArrayList<Integer>> bucketSort(int[] arr, int max, int min) {
/ / barrels
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
// Put each element into the bucket
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// Sort each bucket
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
returnbucketArr; }}Copy the codePrinciple and realization method
First question, what is a barrel? It’s actually a numerical interval, and this is an optimization of bucket sort for counting sort. For the previous extreme case, we solved the problem by dividing it into two bucket sections.
[1,999] is divided into two buckets :(1) [1,500); (2) [500,999]
Then sort the array in the bucket accordingly, and finally we get the sorted array we want.
Why ArrayList?
For bucket sorting, if the numerical distribution is within a bucket interval, it is a concern. If you start by creating buckets that are the same size as the original array, space will be wasted. One reason for using ArrayList is that it has integrated automatic capacity expansion.
Radix sort
The corresponding code
public class RadixSort {
private static void radixSort(int[] array, int d) {
// represents the number of digits corresponding to: 1,10,100...
int n = 1;
// Save the sorted result of each bit for the next bit's sorted input
int k = 0;
int length = array.length;
// The sort bucket is used to store the sorted result after each sorting. The same bucket is used to store the same sorted digit
int[][] bucket = new int[10][length];
// This is used to store the number of digits in each bucket
int[] order = new int[length];
while (n < d) {
// Place each number in the array in the corresponding bucket
for (int num : array) {
int digit = (num / n) % 10;
bucket[digit][order[digit]] = num;
order[digit]++;
}
// Overwrite the data in the bucket generated by the previous loop into the original array to store the sorting result of this bit
for (int i = 0; i < length; i++) {
// The bucket contains data, traverses the bucket from top to bottom and saves the data to the original array
if(order[i] ! =0) {
for (int j = 0; j < order[i]; j++) { array[k] = bucket[i][j]; k++; }}// Set the bucket counter to 0 for the next bit sort
order[i] = 0;
}
n *= 10;
// set k to 0 for the next round of bit sorting
k = 0; }}}Copy the codePrinciple and realization method
This is an iterative process, why say so. The comparison between the high digit and the low digit depends on the presence or absence of the high digit in subsequent calculations. The low comparison is positioned at the beginning of the single digit. In fact, if you sort each digit, that’s what you get when you sum it up.
conclusion
Because the use of the algorithm must take into account the use of the scenario, so the time and space complexity is a prerequisite for the use of the algorithm. But selection and bubble sort are no longer recommended because they are too inefficient.
