The author | shouldn’t meet in the fall

Bubble sort

Bubble sort is undoubtedly one of the most famous sorting algorithms, bubbling from one end of the sequence to the other (you can bubble from left to right, or right to left, depending on your mood) and comparing the size of the two adjacent numbers in turn (depending on your mood).

The illustration bubble

Take [8,2,5,9,7] as an example.

Bubbling from left to right, moving the smaller ones to the right

So let’s compare the size of the first term and the size of the second term, and we see that 2 is less than 8, so let’s leave it where it is. We’re still in eight, two, five, nine, seven.

Move the pointer one space to the right, then compare:

Compare the size of the second and third numbers and find that 2 is less than 5, so the positions are switched and the array is updated to: [8,5,2,9,7].

Move the pointer one more space to the right to continue the comparison:

[8,5,9,2,7] [8,5,9,2,7]

Again, the pointer moves to the right to continue the comparison:

[8,5,9,7,2] [8,5,9,7,2]

In the next step, the pointer moves to the right again and finds that it has reached the bottom. Then the round bubble ends, and the 2 at the far right is the sorted number.

With this constant swapping, the smallest number in the array is moved to the far right.

Next, the second round of bubbling:

Since the 2 on the right is already a sorted number, it no longer participates in the comparison, so this round of bubble ends, and the number 5 at the top of this round of bubble ends up in the ordered sequence, and now the array has changed to [8,9,7,5,2].

Let’s start the third round of bubbling!

Since 8 is larger than 7, its position remains unchanged, and the third round of bubbling has ended. The final result of the third round of bubbling is [9,8,7,5,2].

And then the fourth round of bubbling:

The ratio of 9 to 8 stays the same, that is, 8 is determined to enter the ordered sequence, and then there is only one number left, 9, at the end, from which the sorting ends.

Code implementation

public static void sort(int arr[]){
    for( int i = 0 ; i < arr.length - 1 ; i++ ){
        for(int j = 0; j < arr.length - 1 - i ; j++){ int temp = 0;if(arr[j] < arr[j + 1]){ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; }}}}Copy the code

Bubble code is still quite simple, two layers of circulation, the number of outer bubble rounds, the inner layer in turn, everyone in the river’s lake is known.

When we see nested loops, we should immediately know that this algorithm is O(n2).

The bubbling optimization

One of the biggest problems with bubbling is that it doesn’t matter if you’re ordered or not, you loop through it with your eyes closed.

For example, I take an array example: [9,8,7,6,5], an ordered array, there is no need to sort, it is still a double-layer loop, a lot of data traversal clean, this is actually doing unnecessary things, is a waste of resources.

To solve this problem, we can set up a temporary traversal to indicate whether the array is ordered or not. If so, no traversal is required.

public static void sort(int arr[]){
    for( int i = 0; i < arr.length - 1 ; i++ ){ boolean isSort =true;
        for( int j = 0; j < arr.length - 1 - i ; j++ ){ int temp = 0;if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSort = false; }}if(isSort){
            break; }}}Copy the code

Selection sort

Selection sort of way of thinking is this: first, find the smallest element in an array, carry out, and the first element of an array of exchange it position, the second step, the rest of the elements, continue to look for the smallest element in carrying out, and the second element of an array of swap places, so, until the entire array sorted.

As for choosing big or small, it doesn’t matter, you can also choose the biggest row each time, or you can choose the smallest row each time, as long as your sorting method is this way, it is called selection sorting.

The illustration selected row

Let’s take [8,2,5,9,7] as an example.

For the first selection, find the smallest number in the array, 2, and then switch places with the first number. (If the first number is the minimum, then you can swap places with yourself without doing anything, it’s an if thing.)

On the second choice, since the first position in the array is already sorted, you just need to find the smallest number in the remaining position, 5, and swap with the second position in the array.

For the third selection, find the minimum value of 7 and switch positions with the element in the third position.

On the fourth selection, find the minimum 8 and swap positions with the element in the fourth position.

The last one reaches the end of the array, there’s nothing to compare, and the selection ends.

So the whole array is sorted.

Code implementation

public static void sort(int arr[]){
    for( int i = 0; i < arr.length ; i++ ){ int min = i; // The index of the smallest elementfor(int j = i + 1; j < arr.length ; j++ ){if(arr[j] < arr[min]){ min = j; Int temp = arr[I]; arr[i] = arr[min]; arr[min] = temp; }}Copy the code

Double loop, exactly the same time as bubbling, order n2.

Insertion sort

Insert sort of thought and we play poker touch cards, from the pile of a card to touch up the cards are disorderly, we will touch the card inserted into the left hand in the appropriate position, so that the left hand in the card time to maintain an orderly state.

What if instead of drawing cards from the deck, we initialize them in the left hand and it’s a mess? Again, we put the right side of the card to hand moving over a little, put his hand to empty out a little to the left of the position, and then draws a disorderly card, insert to the left, and then draws a, insert to the left, then draws a, insert to the left, each insert is inserted into the appropriate position on the left, keep to the left of the card is ordered, finished, until the right of the brand, the sequence.

The illustration strip

Array initialization: [8,2,5,9,7], we divide the data in the array into two regions, sorted region and unsorted region. At initialization, all data is in the unsorted region, sorted region is empty.

So in the first round, we take a random number from the unsorted region, and since it’s random, we take the first number, and we insert it into the sorted region, and the sorted region is empty, so we don’t compare, and by default it’s already sorted. (Of course, the first round can be omitted in the code, starting with the element with subscript 1.)

In the second round, continue to take a number from the unsorted area and insert it into the sorted area. At this time, you need to traverse the sorted area and compare the numbers one by one, depending on whether you want to sort in ascending order or in reverse order. Here’s the ascending order:

Round 3, Row 5:

Round 4, Row 9:

Round five, row seven

End of sorting.

Code implementation

public static void sort(int[] arr) {
    int n = arr.length;
    for(int i = 1; i < n; ++i) { int value = arr[i]; int j = 0; // Insert positionfor (j = i-1; j >= 0; j--) {
            if(arr[j] > value) { arr[j+1] = arr[j]; // move data}else {
                break; } } arr[j+1] = value; // Insert data}}Copy the code

As we can see from the code, if I find the right place, I will not compare, just like a card drawn from the deck is smaller than my hand, so I just put it at the end of the line, instead of moving the data one by one to make room to insert it into the middle.

So, the best case is O(n), the worst case is O(n2), but the time complexity metric looks at the worst case, not the best case, so the insertion sort is O(n2).

Hill sorting

Hill sort, named after its inventor Hill, is also called “reduced incremental sort”, a more efficient and improved version of insertion sort.

As we know, the efficiency of insertion sort is relatively slow for large-scale random number groups, because it can only move the data one bit at a time. In order to speed up the insertion speed, hill sort allows the data to jump when moving, saving part of the time cost.

Graphic Hill sort

Array 10 data to sort:

Assuming the calculated sorting interval is 4, our first comparison should be with the 5th data compared to the 1st data.

The transposed data is [7,2,5,9,8,10,1,15,12,3], then the pointer moves right and the sixth data is compared to the second data.

Move the pointer to the right and continue the comparison.

If, after data exchange, data still exists in the position obtained by subtracting the interval, continue to compare, for example, in the figure below, 12 is compared with 8. After standing still, the pointer jumps from 12 to 8. After subtracting the interval, there is another data 7 with subscript 0 in front of it, so 8 is compared with 7.

The result is that the numbers 7, 8, and 12 are arranged in order.

When the last element is compared, we see that most of the larger values seem to be adjusted to the middle and lower parts of the array.

If we have a long array, say 100, then we’re going to have a range of 40 or 50, and then we’re going to have a range of 10 or 20, and then we’re going to have a range of one, and then we’re going to have a range of 1.

Move the pointer right to continue the comparison:

Repeat the steps, you can complete the sorting, repeat the graph is not drawn.

And we can see that when the interval is 1, the sort it uses is insertion sort.

Code implementation

public static void sort(int[] arr) { int length = arr.length; // interval int gap = 1;while (gap < length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for(int i = gap; i < length; i++) { int tmp = arr[i]; int j = i - gap; // sort across regionswhile(j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap = gap / 3; }}Copy the code

You may ask why the interval should be calculated with gap = gap*3 + 1. In fact, there is no answer for the optimal interval calculation method. This is a long-standing problem that has not been solved, but it is almost always taken around 1/2 to 1/3.

Merge sort

Merge literally means merge, and the core idea of merge is divide-and-conquer, where you cut an array in half, recursively, until you cut it into a single element, and then you reassemble and merge it, and then you merge it into a small array, and then you combine two decimals into a large array, and then you merge it and sort it.

Graphical merge sort

Let’s take [8,2,5,9,7] as an example

First, cut it in half:

Cut to:

Cut again

When the granularity is cut to the minimum, merge begins

The number of numbers is small for the sake of the diagram, and singular for the sake of the details. I’ve drawn a more intuitive picture below that you might like better:

Code implementation

As we mentioned above, the core idea of merge sort is divide and conquer, divide and conquer, divide and conquer, break a big problem into numerous smaller problems and then merge them. Here we use recursive implementation:

public static void sort(int[] arr) { int[] tempArr = new int[arr.length]; Sort (arr, tempArr, 0, arr. Length-1); } /** * merge sort * @param arr sort array * @param tempArr temporary storage array * @param startIndex sort start * @param endIndex sort end */ private Static void sort(int[] arr, int[] tempArr, int startIndex, int endIndex){if(endIndex <= startIndex){
            return; } // int middleIndex = startIndex + (endIndex - startIndex) / 2; // Sort (arr, tempArr, startIndex, middleIndex); Sort (arr, tempArr, middleIndex + 1, endIndex); // Merge (arr, tempArr, startIndex, middleIndex, endIndex); } /** * merge * @param arr sort array * @param tempArr temporarily store array * @param startIndex merge start * @param middleIndex merge middle * @param */ private static void merge(int[] arr, int[] tempArr, int startIndex, int middleIndex, Int endIndex) {// Copy the data to be mergedfor(int s = startIndex; s <= endIndex; s++) { tempArr[s] = arr[s]; } int left = startIndex; Int right = middleIndex + 1; // first subscript on the rightfor (int k = startIndex; k <= endIndex; k++) {
            if(left > middleIndex){// if the left index is larger than the middleIndex, the left index is exhausted. arr[k] = tempArr[right++]; }else if(right > endIndex){// If the index on the right is larger than the array length, the data on the right is exhausted. arr[k] = tempArr[left++]; }else if(tempArr[right] < tempArr[left]){ arr[k] = tempArr[right++]; // Type the first digit on the right, then the right subscript pointer +1. }else{ arr[k] = tempArr[left++]; // Type the first digit on the left, then the left subscript pointer +1. }}}Copy the code

We can find that there is only one for loop in the merge method, and we can directly conclude that the time complexity of each merge is O(n), while the split array is divided in half, which belongs to logarithmic time O(log n), which is equal to O(log2n). In other words, The total time is O(nlogn).

In terms of space complexity, most people write merges by merging temporary arrays in the merge method, which is O(n). In this case, I merge in place, and only apply a temporary array at the beginning, so the space complexity is O(1).

Quick sort

The core idea of quicksort is also divide-and-conquer, divide and conquer. Its realization way is basic value each choose one from the sequence of several other basic value and in turn, is put on the right, bigger than basic value smaller than benchmark put on the left, then to the left and the right number of two groups were chosen a benchmark, comparing the same movement, repeat steps, until the end into a single element, the entire array is orderly sequence.

The illustration fast row

Let’s illustrate with [8,2,5,0,7,4,6,1]

First, we randomly select a baseline value:

Compare with other elements in order, large on the right and small on the left:

Then we arrange the data on the left in the same way:

Continue to row 0 and 1:

Since there is only one number left, there is no need to arrange it. The array sequence now looks like this:

The right side with the same operation, can be sorted to complete.

Unilateral scanning

The key to quicksort is sharding, which involves comparing and moving, and this is a technique called unilateral scanning.

We randomly select a number as the base value, and set a mark to represent the right-most subscript position of the left sequence, of course, starting with 0. Then we iterate over the number array, and if the element is greater than the base value, no operation, continue to iterate, and if the element is less than the base value, mark + 1, Then exchange the position of the element where Mark is located with the element traversed. Mark stores data smaller than the reference value. When the traversal is over, exchange the position of the reference value with the element where Mark is located.

Code implementation:

Public static void sort(int[] arr) {sort(arr, 0, arr. Length - 1); } private static void sort(int[] arr, int startIndex, int endIndex) {private static void sort(int[] arr, int startIndex, int endIndex) {if (endIndex <= startIndex) {
        return; } // partition int pivotIndex = partitionV2(arr, startIndex, endIndex); Sort (arr, startIndex, pivotIndex-1); Sort (arr, pivotIndex+1, endIndex); } private static int partition(int[] arr, int startIndex, int endIndex) {private static int partition(int[] arr, int startIndex, int endIndex) {int pivot = arr[startIndex]; Int mark = startIndex; //Mark is initialized to the starting subscriptfor(int i=startIndex+1; i<=endIndex; i++){
        if(arr[I]<pivot){// less than pivot mark+1, and switch positions. mark ++; int p = arr[mark]; arr[mark] = arr[i]; arr[i] = p; Arr [startIndex] = arr[mark]; arr[mark] = pivot;return mark;
}
Copy the code

Bilateral scanning

There is another way of doing bilateral scanning, which seems more intuitive: We randomly recruited a number as a benchmark, and then from the left and right sides, scanning array from left to right to find a basic value is greater than the first elements, record the subscript pointer, and then turn to scan from right to left, to find a less than basic value elements, exchanging the positions of the two elements, repeat steps, until about two Pointers meet, The base value is then swapped with the rightmost element on the left.

Let’s look at the implementation code. The only difference is the partition method:

Public static void sort(int[] arr) {sort(arr, 0, arr. Length - 1); } private static void sort(int[] arr, int startIndex, int endIndex) {private static void sort(int[] arr, int startIndex, int endIndex) {if (endIndex <= startIndex) {
        return; } pivotIndex = partition(arr, startIndex, endIndex); Sort (arr, startIndex, pivotIndex-1); Sort (arr, pivotIndex+1, endIndex); } private static int partition(int[] arr, int startIndex, int endIndex) {int left = startIndex; int right = endIndex; int pivot = arr[startIndex]; // take the first element as the reference valuewhile (true) {// Scan from left to rightwhile (arr[left] <= pivot) {
            left++;
            if (left == right) {
                break; // Scan from right to leftwhile (pivot < arr[right]) {
            right--;
            if (left == right) {
                break; }} // The left and right Pointers meetif (left >= right) {
            break; Int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } // Insert the datum into the sequence int temp = arr[startIndex]; arr[startIndex] = arr[right]; arr[right] = temp;return right;
}
Copy the code

extreme

The time complexity of quicksort is the same as merge sort, O(n log n), but this is based on the assumption that each shred can cut the array in half about the same size. If extreme cases occur, such as sorting an ordered sequence, such as [9, 8, 7, 6, 5, 4, 3, 2, 1], select the base value 9. In this case, the time complexity is reduced to O(N2). Of course, the probability of extreme cases is also relatively low.

Therefore, the time complexity of quicksort is O(nlogn), which will degenerate to O(n2) in extreme cases. In order to avoid the occurrence of extreme cases, the selection of reference values should be randomly selected, or the array should be shuffled before selection.

In addition, the space complexity of quicksort is O(1).

Heap sort

Heap sort, as its name implies, is an algorithm that uses heap data structure to sort.

If you’re not familiar with heap data structures, check out Wu’s previous series on data structures – watching animations to understand heap easily

If you’re familiar with the data structure heap, you should know that heap is a priority queue, and there are two implementations, maximum heap and minimum heap, and since we sort in ascending order here, we’ll just call it maximum heap.

We can all identify the heap (the default for the mass of all) as a complete binary tree, but located at the top of the heap element is always a maximum of the whole tree, each node values are smaller than the parent node, due to the heap to keep such rules features, so once the inside of the heap data changes, we must be carried out on the heap to build at a time.

Since the top element is always the maximum value in the whole tree, shouldn’t we just take the element from the top of the heap after we put the data into a heap? The first time you take an element, is that the maximum? And then we rebuild the heap, and then we take the element at the top of the heap, is that the second largest value? You take it over and over again, and the data that you take out is the ordered data.

The illustration heap row

Let’s illustrate with [8,2,5,9,7,3].

First, build the array into a heap.

Now that we’ve built the heaps, we take the top of the heap, which is 9, by swapping the first and last bits of the array, and then changing the range of the array to be sorted to -1.

Now the data to be sorted is [3,8,5,2,7] and we continue to build piles of the data to be sorted.

Fetching the top of the heap, this time the first and last bits are swapped, because the edge to be sorted has been reduced by 1.

Continue building the heap

The data pulled from the top of the heap eventually forms an ordered list, so we don’t need to repeat the steps, so let’s look at the code implementation.

Code implementation

public static void sort(int[] arr) { int length = arr.length; // buildHeap buildHeap(arr, length);for( int i = length - 1; i > 0; Int temp = arr[0]; int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // Array length -1 hides the last element of the heap. Sink (arr, 0, length); sink(arr, 0, length); }} private static void buildHeap(int[] arr, int length) {for(int i = length / 2; i >= 0; I --) {sink(arr, I, length); Private static void sink(int[] arr, private static void sink(int[] arr, private static void sink(int[] arr, Int index, int length) {int leftChild = 2 * index + 1; Int rightChild = 2 * index + 2; Int present = index; // Drop the subscript of the node to be adjusted to the leftif(leftChild < length && arr[leftChild] > arr[present]) { present = leftChild; } // Sink to the rightif(rightChild < length && arr[rightChild] > arr[present]) { present = rightChild; } // If the subscripts are not equal, the transpose is doneif(present ! Int temp = arr[index]; arr[index] = arr[present]; arr[present] = temp; // Continue to sink(arr, present, length); }}Copy the code

Heap sort and quicksort have the same time order nlogn.

Count sorting

Counting sort is a kind of sorting algorithm that is not based on comparison. The sorting algorithm we introduced before is almost based on comparison between elements to sort. The time complexity of counting sort is O(n + m), m refers to the amount of data, and the time complexity of counting sort algorithm is about O(n). Faster than any comparison sorting algorithm.

Diagram to count

The following is illustrated with the numbers [3,5,8,2,5,4].

First, we find the largest number in the set, which is 8, and create an empty array arr with a maximum subscript of 8.

Iterate over the data and fill the number of occurrences of data into the corresponding subscript position in arR.

Iterate over the ARR and pull out the data in turn.

Code implementation

Public static void sort(int[] arr) {int Max = arr[0];for (int i = 1; i < arr.length; i++) {
        if(arr[i] > max) { max = arr[i]; Int [] countArr = new int[Max + 1]; / / countfor(int i = 0; i < arr.length; i++) { countArr[arr[i]]++; arr[i] = 0; } // sort int index = 0;for (int i = 0; i < countArr.length; i++) {
        if(countArr[i] > 0) { arr[index++] = i; }}}Copy the code

A stable sort

There is a requirement that when ranking results, the person who is at the top of the list is still ahead of the person who is at the same level.

We know countArr stores the number of occurrences of a score, so we can actually calculate the maximum ranking of each score by summation each element of countArr.

The diagram below:

What does it mean to transform?

If we take the array [2, 5, 8, 2, 5, 4] and go to countArr, you will find that the value of 3 in countArr[3] is 2, representing the second place (because the first place is the smallest 2, right?). The value of 5 in countArr[5] is 5. Why 5? [2,3,4,5,5,8] [5, 5, 8] CountArr [4] has a value of 3, which is the third place, and 5 is the fifth place because there are two numbers of 5, which naturally occupy the fourth and fifth places.

So we should be careful to take the data from the array from right to left, and subtract countArr by 1 when we take the data from countArr, so that when we take the data from countArr again, we can take the data from countArr by one.

Corresponding code implementation:

Public static void sort(int[] arr) {int Max = arr[0];for (int i = 1; i < arr.length; ++i) {
        if(arr[i] > max) { max = arr[i]; Int [] countArr = new int[Max + 1]; / / countfor(int i = 0; i < arr.length; ++i) { countArr[arr[i]]++; } // sequential summationfor(int i = 1; i < max + 1; ++i) { countArr[i] = countArr[i-1] + countArr[i]; } // Sort array int[] sortedArr = new int[arr.length]; / / sortingfor(int i = arr.length - 1; i >= 0; --i) { sortedArr[countArr[arr[i]]-1] = arr[i]; countArr[arr[i]]--; } // Copy the sorted data to the original arrayfor(int i = 0; i < arr.length; ++i) { arr[i] = sortedArr[i]; }}Copy the code

Count limitation

Counting sort has a lot of bugs, so let’s look for bugs.

What if THE data I’m sorting has zeros in it? Int [] initializes all zeros.

What if I want to sort through a larger range of data? For example [1,9999], I row two numbers and you want to create an array of int[10000] to count?

For the first bug, we can fix it by using offsets. For example, if I want to arrange the numbers [-1, 0, -3], this is easy, I’ll add 10 to all of them, and then subtract 10 when I write back to the original array. But you might stumble, if you happen to have a -10 in your array, and you add 10 to it and it becomes a 0 again.

For the second bug, it really cannot be solved. If the value of [9998,9999] is large but not within the same range, we can also use offset to solve the problem. For example, for these two data, I only need to apply an array of int[3] after deducting 9997.

It can be seen that counting sort is only suitable for positive integers and the value range of the array sort is not different, its sort speed is very considerable.

Bucket sort

Bucket sort can be regarded as an upgraded version of counting sort. It divides the data to be sorted into multiple ordered buckets. The data in each bucket is sorted separately, and then the data in each bucket is taken out in turn to complete sorting.

Illustrated bucket sorting

Let’s take a set of data [500,6123,1700,10,9999] that can’t be chewed up by counting sort.

Step one, we create 10 buckets, Install data in the range of 0-1000, 1000-2000, 2000-3000, 3000-4000, 4000-5000, 5000-6000, 6000-7000, 7000-8000, and 8000-9000 respectively.

Step 2, iterate through the array and add the check to the bucket.

In the third step, the data in the bucket is sorted separately. Only the number in the first bucket is greater than 1, obviously only the first bucket is needed.

Finally, take out the data in the bucket one by one and finish sorting.

Code implementation

This bucket sorting may seem simple at first glance, but there are a few things to consider when typing code.

What do I mean by a bucket?

How do I determine the number of buckets?

What is the method of bucket sorting?

The code is as follows:

Public static void sort(int[] arr){// Max = arr[0]; int min = arr[0]; int length = arr.length;for(int i=1; i<length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        } else if(arr[i] < min) { min = arr[i]; Int diff = max-min; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();for(int i = 0; i < length; i++){ bucketList.add(new ArrayList<>()); } // The storage range for each bucketfloat section = (float) diff / (float) (length - 1); // Add data to bucketfor(int i = 0; i < length; Int num = (int) (arr[I] / section) -1;if(num < 0){ num = 0; } bucketList.get(num).add(arr[i]); } // Bucket sortfor(int i = 0; i < bucketList.size(); I ++){// The collections.sort (bucketlist.get (I)); } // write the original array int index = 0;for(ArrayList<Integer> arrayList : bucketList){
        for(int value : arrayList){ arr[index] = value; index++; }}}Copy the code

Buckets are, of course, collections that can hold data, so I’m using an arrayList, and if you use a LinkedList that’s fine.

I think it’s reasonable to set the number of buckets to the length of the original array, because ideally one bucket per data.

The data bucket mapping algorithm is actually an open question, I admit that the solution I wrote here is not good, because I have tested different data sets to sort, if you have a better solution or idea, feel free to leave a comment.

For convenience, in-bucket sorting uses the sorting method provided by the current language. If stable sorting is required, you can choose to use a custom sorting algorithm.

Thinking and application of bucket sorting

In the case of sufficient extra space, the number of buckets can be increased as much as possible. In the limit case, when there is only one data per bucket or only one value per bucket, the operation of in-bucket sorting can be completely avoided, and the optimal time complexity of bucket sorting can reach O(n).

For example, with 750 sats and millions of people in the country, all we have to do is create 751 buckets, loop through them and throw them in one by one, sorting them in milliseconds.

However, if the data is divided into buckets, the data distribution among buckets is very uneven. Some data are very large and some data are very small. For example, we divide the ten data [8,2,9,10,1,23,53,22,12,9000] into ten buckets. This is a very inefficient situation, which reduces the time complexity to O(nlogn). The solution is to judge the amount of data in the bucket every time we sort the bucket. If the amount of data in the bucket is too large, we should call back in the bucket to sort the bucket again.

Radix sort

Radix sort is a kind of non-comparative integer sort algorithm, its principle is to cut the data into different numbers according to the number of digits, and then compare each number separately. Suppose we were to sort a million mobile phone numbers. What sort algorithm should we choose? The fast sorting is merging, the quick sorting time complexity is O(nlogn), count sort and bucket sort although faster, but the number of mobile phone number is 11 digits, how many buckets is needed? The memory module refuses to accept the request.

At this point, it’s best to use radix sort.

Graphic base line

Let’s use the numbers [892, 846, 821, 199, 810,700] as an example.

First, create ten buckets to aid sorting.

The units digit is sorted first, and the data is put into the bucket corresponding to the subscript value according to the value of the units digit.

After the row, we take the data out of the bucket in turn.

So next, let’s do the tens.

And finally, hundreds.

Sorting done.

Code implementation

Radix sort can be seen as an extension of bucket sort, also with buckets to assist sort, code as follows:

public static void sort(int[] arr){ int length = arr.length; Int Max = arr[0];for(int i = 0; i < length; i++){if(arr[i] > max){ max = arr[i]; Int location = 1; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(); // Load data with remainder 0-9 with length 10for(int i = 0; i < 10; i++){
        bucketList.add(new ArrayList());
    }

    while(trueInt dd = (int) math.pow (10, (location-1));if(max < dd){
            break; } // Data is stored in bucketsfor(int i = 0; i < length; Int number = ((arr[I] / dd) % 10); bucketList.get(number).add(arr[i]); } // write back to array int nn = 0;for(int i=0; i<10; i++){ int size = bucketList.get(i).size();for(int ii = 0; ii < size; ii ++){ arr[nn++] = bucketList.get(i).get(ii); } bucketList.get(i).clear(); } location++; }}Copy the code

In fact, its idea is very simple, no matter how big your number is, according to the row one by one, 0-9 is only ten barrels at most: first by the position of low weight, then by the position of heavy weight.

Of course, if you have a need, you can also choose to go from high to low.

conclusion

Thank you for reading here, and I hope this article will give you a clear understanding of the top 10 most commonly used sorting algorithms.