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

This article mainly introduces the relevant knowledge of Java bubble sorting case analysis, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this Java bubble sorting case analysis article. Let's take a look at it.

The situation was like this. At that time, it was OK to talk to the interviewer. Just when he felt as if he was almost finished, the interviewer threw him a question: "I happen to have pen and paper. Please write a bubble sort."

The reader panicked, not because he couldn't write, because as a programmer, there was basically nothing about bubble sorting that couldn't be written, but because things happened all of a sudden and felt bad. This is what he wrote at the time:

Public void bubbleSort (int [] source) {

For (int I = source.length-1; I > 0; iMurray -) {

For (int j = 0; j

A [jambo1])

/ / Exchange, specific implementation strategy

Swap (source, j, juni1)

}

}

}

Sure enough, after he wrote it, the interviewer asked him, is there anything wrong with this way of writing? Can we continue to optimize? As a result, I really didn't answer. Seeing this, readers might as well think about how to optimize it first. )

Today, this bubble sort, let's talk a few more words, return to the classic. I also hope that in the future, whether we have friends for internship or school recruitment, we will not fall on the same problem again.

The time complexity of the bubble sorting algorithm is high, if you are not clear how to calculate the algorithm complexity, you can refer to this article: learn the time complexity and space complexity step by step. But bubbling sort is simple, the basic process is: each round from the beginning of a pairwise comparison, put the larger items on the right side of the smaller items, so that each round to ensure that the maximum number is on the far right. How to achieve it? As the above friend wrote, basically everyone can write.

But today's main discussion is how to optimize, some people may say, this is the simplest algorithm, what else can be optimized? Indeed, there is nothing wrong with the above code, but there is room for optimization.

We can assume that a scenario, such as 8 1 2 3 5 7 7, after a sort, the result becomes 1 2 3 5 7 8, so is it necessary for us to continue to cycle as in the code above? It must not be necessary, because this is the final result.

For the above code, the main point of our optimization is that if a certain sort has been ordered, we need to reduce the number of sorted trips. Otherwise, a lot of useless work would have been done.

In order to solve this problem, we can consider adding a Boolean variable to the algorithm to identify whether the round has exchanged data or not. if the exchange of data locations is not found in a certain sort, it means that all the items in the unordered area to be sorted have satisfied the sorted results. Then there is no need to sort again. It can be modified as follows:

Public void bubbleSort (int [] source) {

Boolean exchange

For (int I = source.length-1; I > 0; iMurray -) {

Exchange = false

For (int j = 0; j

A [juni1]) {

Swap (source, j, juni1)

Exchange = true

}

}

If (! exchange) return

}

}

This is the end of the optimization, in fact, the code logic is very simple, through a Boolean variable can monitor the process whether there is a data exchange.

The best case of bubble sorting is that the initial state is positive, and the sorting can be completed in one scan, so the best time complexity is O (N); in the worst case, it is reverse, and the worst time complexity is O (N ^ 2). On average, there are 2 cycles in each round, and the time complexity of N round is O (N ^ 2). So it's not a good sorting algorithm. This is the end of the discussion of this issue, if there is a better optimization algorithm, you are welcome to leave a message for discussion.

Bubble sorting is not good, but why would the interviewer ask? What do we need to pay attention to this matter?

1. Classic things, may not be used, but from the classic things, we can still learn a lot, otherwise it will not become a classic. Especially for those who are often asked in interviews, there is always a reason for its existence.

two。 What is in the textbook does not represent actual combat, so in many cases, it may not be so applicable when considering non-ideal circumstances. Interviewers tend to pay more attention to how the interviewer responds when it is not applicable. The interviewer pays more attention to the interviewer's thinking.

3. Fresh students can not be impetuous, especially when preparing for the interview, must step by step, do not aim too high, dabble in, and learn more about classical data structures and algorithms (the most commonly used classical data structures and algorithm summaries). It is necessary to do more algorithm questions.

This is the end of the article on "case Analysis of Java Bubble sorting". Thank you for reading! I believe you all have a certain understanding of the knowledge of "Java Bubble sorting case Analysis". If you want to learn more, you are welcome to follow the industry information channel.

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.