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

This article introduces the relevant knowledge of "how to achieve quick sorting". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Overview

Quick sorting is also a typical application of divide-and-conquer idea in sorting algorithm. In essence, quick sorting should be regarded as a recursive divide-and-conquer method based on bubble sorting.

The name of quick sort is simple and rude, because as soon as you hear the name, you know the meaning of its existence, that is, fast and efficient! It is one of the fastest sorting algorithms to deal with big data.

Algorithm step

Pick an element from a series, called a "pivot"

Reorder the series so that all elements smaller than the benchmark are placed in front of the benchmark, and all elements larger than the benchmark are placed behind the benchmark (the same number can be on either side). After the partition exits, the datum is in the middle of the series. This is called a partition operation

Recursive sorts the subseries of elements less than the reference value and the subseries of elements greater than the reference value

First, let's take a look at the partition operation:

Original array:

We take the first element'5' of the array as the "datum", and then define two pointers "I" and "j" pointer "I" to move from left to right at the position of the first element after the datum. Each time we move, we need to compare the size of the "I" position element with the reference value. If it is less than the benchmark value, execute "swap" once, that is, exchange the values of the "I" and "j" elements. In addition, each time "swap" is executed, the value of "j" is increased by one.

Ok, "j" does not move for a while, "I" moves back, when "I" moves to the position of "1"

At this point, "1" is less than the benchmark value "5", and "swap" needs to be executed once, and "j" plus one is required.

And so on, when "I" moves to the far right, the result is as follows:

At this point, we only need to exchange the values of the previous position of "base value" and "j" (that is, 5 and 2) to achieve the effect of "partition".

I think we can see that all the elements that are smaller than the benchmark are placed in front of the benchmark, and all the elements that are larger than the benchmark are placed behind the benchmark.

If you look closely, you will find that the pointer "I" is used to scan the array elements, and the left side of the pointer "j" is always smaller than the benchmark element, which is why the base value is exchanged with the previous element of "j".

At this point, a round of "partition" operation is complete.

Let's look at the whole process:

Code:

Public static int [] sort (int [] arr) {return quickSort (arr, 0, arr.length-1);} private static int [] quickSort (int [] arr, int left, int right) {if (left < right) {/ / partition int partitionIndex = partition (arr, left, right); quickSort (arr, left, partitionIndex-1); quickSort (arr, partitionIndex + 1, right) } return arr;} private static int partition (int [] arr, int left, int right) {int pivot = left; / / pointer j int j = pivot + 1; for (int I = j; I

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.