Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to understand the sorting algorithm". The content in the article is simple and clear, and it is easy to learn and understand. please follow the editor's train of thought to study and learn "how to understand the sorting algorithm".

Sorting is a problem that we often face in our lives. in PE class, the teacher will let us arrange from short to high, and when we take the postgraduate entrance examination, the scores will be sorted from the top to the bottom (readers of the postgraduate entrance examination. You will certainly receive a big envelope from your favorite school). When we shop online, we sometimes list the goods that best meet our expectations in the order of sales volume from high to low and price from low to high. These are all examples in our lives.

Sorting concept: the process of sorting disorganized data elements by keyword order through a certain method (sorting algorithm) is called sorting. For example, our sales volume and price above are the keywords.

Stability of sorting algorithm

What is the stability of the sorting algorithm?

Because there may be records with two or more equal keywords in the sequence of records to be sorted, and the sorting results may not be unique, so after we sort, if the original order between the equal elements remains the same. The sorting method used is said to be stable, otherwise it is called unstable. See the picture below

For example, in the figure above, we have two identical elements 4 in our array. We sort them with different sorting algorithms. After the algorithm is sorted, the relative position of the two same elements does not change. We call it a stable sorting algorithm. If the relative position of algorithm 2 changes after sorting, it is an unstable sorting algorithm.

What is the use of the stability of the sorting algorithm?

In most of our exercises, we only sort the array, we only need to consider the time complexity, space complexity and other indicators, the stability of the sorting algorithm is generally not considered. However, the stability of sorting algorithm is a particularly important indicator in real software development. Let's go back to our example just now. We want to rank the year-end bonus from less to more, and then rank the number of red beans in the same year-end bonus range from less to more.

The stability of the sorting algorithm is very important here. Why is that? See the picture below

After the first ranking, all the employees were ordered from less to more according to the number of red beans.

In the second sorting, we use a stable sorting algorithm, so after the second sorting, the employees with the same year-end bonus still keep the order of red beans (the relative position remains the same), and red beans are still sorted from small to big. We use a stable sorting algorithm, which only needs to sort twice.

Stable sorting allows the results of the first keyword sort to serve those numbers that are numerically equal in the second keyword sort.

In the above case, if we use unstable sorting algorithm, it is very complicated to achieve this effect.

Comparative and non-comparative classes

We determine the relative order of elements based on whether they rely on comparison with other elements. In order to distinguish between the comparative sorting algorithm and the non-comparative sorting algorithm.

Inner sort and outer sort

Internal sorting is that all records to be sorted are placed in memory during the whole process of sorting. External sorting is due to the fact that there are too many sorting records to be placed in memory at the same time, and the whole sorting process needs to exchange data between internal and external memory for many times. common internal sorting algorithms are: insert sort, Hill sort, select sort, bubble sort, merge sort, fast sort, heap sort, cardinality sort and so on.

For our internal sorting, we are mainly affected by three aspects: time performance, auxiliary space, and algorithm complexity.

Time performance

During the execution of our sorting algorithm, we mainly compare and exchange two kinds of operations. comparison is the most basic operation of the sorting algorithm, and moving refers to the movement of records from one location to another. Therefore, an efficient sorting algorithm should be compared and moved as little as possible.

Auxiliary space

The amount of auxiliary space needed to execute the algorithm is also an important indicator to measure the performance of the sorting algorithm.

Complexity of the algorithm

The complexity of the algorithm here does not refer to the time complexity of the algorithm, but to the complexity of the algorithm itself. Too complex algorithms will also affect the performance of sorting.

Let's first review two simple sorting algorithms, bubble sorting and simple selection sorting, to see if there are any things that were ignored before. It will continue to be serialized later, summarizing both common and practical sorting algorithms.

Bubble sort (Bubble Sort)

When we learn sorting in various algorithm books, the first estimate is bubbling sorting. The main reason is that this sorting algorithm is the simplest and easiest to understand. (it may also have a good name, ). The old buddies who have learned are also going to review it. Let's dig into the bubble sorting together.

The basic idea of bubble sorting is to compare the keywords of adjacent records in pairs and exchange them if they are in reverse order until there is no reverse order. Bubble sorting one bubble will move at least one element to where it should be, so if the array has n elements, the sort must be completed after repeating n times. According to the definition, bubbling sort is obviously a kind of comparative sort.

The simplest sorting implementation

Let's take a look at this code first.

Class Solution {public int [] sortArray (int [] nums) {int len = nums.length; for (int I = 0; I)

< len; ++i) { for (int j = i+1; j < len; ++j) { if (nums[i] >

Nums [j]) {swap (nums,i,j);} return nums;} public void swap (int [] nums,int iMint j) {int temp = nums [I]; nums [I] = nums [j]; nums [j] = temp;}}

Let's think about the above code, and let the keywords nums [I] and nums [j] compare each time if nums [I] > nums [j], then swap, so that nums [0] must be the minimum after a loop.

So is this code bubbling sort? Obviously not, our idea of bubble sorting is to compare the keywords of adjacent records in pairs. note that there are adjacent records, so this code is not our bubble sort. Let's use a motion diagram to simulate the execution process of bubble sort. After reading it, you can definitely write an authentic bubble sort.

Bubble sort code

Class Solution {public int [] sortArray (int [] nums) {int len = nums.length; for (int I = 0; I)

< len; ++i) { for (int j = 0; j < len - i - 1; ++j) { if (nums[j] >

Nums [juni1]) {swap (nums,j,j+1);} return nums;} public void swap (int [] nums,int iline int j) {int temp = nums [I]; nums [I] = nums [j]; nums [j] = temp;}}

The code in the figure above is the authentic bubble sorting code, but did we find this problem?

At this time, the array is completely ordered and can be returned directly, but it is not returned in the dynamic diagram, but continues to be executed, so what can we do to make it return directly when it is in complete order and not continue to execute?

Let's imagine that we compare through nums [j] and nums [jacks 1], and if it's larger than that, then we swap, and we imagine that if we have a completely ordered array, we sort bubbles, and we don't have to swap every time we compare. So if no exchange takes place, it means that the current order is completely orderly.

Can we judge whether an exchange has taken place by a flag bit? Of course you can.

Let's improve the bubble sorting.

Improved bubble sorting code

Class Solution {public int [] sortArray (int [] nums) {int len = nums.length; / / flag bit boolean flag = true; / / Note the for loop condition for (int I = 0; I)

< len && flag; ++i) { //如果没发生交换，则依旧为false，下次就会跳出循环 flag = false; for (int j = 0; j < len - i - 1; ++j) { if (nums[j] >

Nums [juni1]) {swap (nums,j,j+1); / / if an exchange occurs, it becomes true. Next time, continue to judge flag = true;} return nums. } public void swap (int [] nums,int iMint j) {int temp = nums [I]; nums [I] = nums [j]; nums [j] = temp;}}

In this way, we avoid meaningless circular judgments that are already orderly.

Time complexity analysis

In the best case, when the tables to be sorted are completely ordered, according to the improved code, we only need to traverse once, only n-1 comparisons, and the time complexity is O (n).

In the worst case, that is, when the sorting table is in reverse order, you need to compare (nmur1) + (nmur2) +. + 2 + 1 = n * (nmur1) / 2, and the exchange of equal order of magnitude, then the time complexity is O (n ^ 2).

On average, n * (nmur1) / 4 exchange operations are required, and the comparison operation is greater than or equal to the exchange operation, and the upper limit of complexity is O (n ^ 2), so the average time complexity is O (n ^ 2).

Space complexity analysis

Because bubble sorting is only an exchange operation between adjacent elements, only a constant order of extra space is used, so the space complexity is O (1).

Stability analysis

So is the bubble sort stable? Of course, it is stable, in our code, when nums [j] > nums [j + 1], it will be exchanged, but not when it is equal, and the relative position of the equivalent elements has not changed, so the bubbling sort is stable.

Simple selection sort (Simple Selection Sort)

Our bubble sorting is constantly exchanged, and through the exchange to complete the final sorting, our idea of simple selection sorting is also easy to understand. The main idea is that we select the record with the lowest keyword in each n-i+1 record as the I record of the ordered sequence, as shown in the following figure.

For example, in the image above, green represents sorted elements and red represents unsorted elements. If our current pointer points to 4, we traverse the red element to find the minimum value, and then swap with 4. We found that the selection sort can relocate at least 1 element after performing a loop.

Let's take a look at the execution process of the code. After looking at it, we will be able to write the code.

Note: to make it easier to understand, the min value holds the value, not the index. In the actual code, the index is saved.

Simple selection sort code

Class Solution {public int [] sortArray (int [] nums) {int len = nums.length; int min = 0; for (int I = 0; I

< len; ++i) { min = i; //遍历找到最小值 for (int j = i + 1; j < len; ++j) { if (nums[min] >

Nums [j]) min = j;} if (min! = I) swap (nums,i,min);} return nums;} public void swap (int [] nums, int I, int j) {int temp = nums [I]; nums [I] = nums [j]; nums [j] = temp;}}

Time complexity analysis

From the point of view of the process of simple selection and sorting, his greatest feature is that the number of times of exchanging moving elements is quite small, which saves sorting time. Simple selection is different from bubbling sorting. We find that no matter the best case and the worst case, the number of comparisons between elements is the same, I sorting requires n-I comparisons, n represents the number of elements. Then we need to compare (nmur1) + (nmur2) +. + 2 + 1 = n * (nmur1) / 2 times.

For swapping, the best case is to exchange 0 times, and in the worst case (reverse order) to exchange n-1 times. So the time complexity of simple selection sorting is also O (n ^ 2), but its exchange times are much less than bubble sorting, so its efficiency is better than bubble sorting.

Space complexity analysis

From our dynamic graph, we can see that our simple selection sorting only uses a constant order of extra space, so the space complexity is O (1).

Stability analysis

Let's think about it, is the ranking of our simple choices stable?

It is obviously not stable, because we need to find the smallest value behind the pointer and exchange it with the value pointed to by the pointer, as shown in the figure below.

At this point, we need to find the smallest element from the latter element and exchange the pointer to the element, that is, element 2. However, after we exchange, we find that the relative position of two equal elements 3 has changed, so simple selection sorting is an unstable sorting algorithm.

Thank you for your reading, the above is the content of "how to understand the sorting algorithm". After the study of this article, I believe you have a deeper understanding of how to understand the sorting algorithm, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.