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

This article mainly shows you the "java sorting algorithm quick sorting example analysis", the content is easy to understand, clear, hope to help you solve your doubts, the following let Xiaobian lead you to study and learn "java sorting algorithm quick sorting example analysis" this article.

A brief introduction

Quick sort (Quicksort) is an improvement on bubble sorting.

Basic thought

The quick sort algorithm achieves sorting through multiple comparisons and exchanges, and the sorting process is as follows:

(1) first set a demarcation value (base value), by which the array is divided into left and right parts.

(2) centralize the data that is greater than or equal to the boundary value to the right side of the array, and the data less than the boundary value to the left side of the array. At this point, each element in the left part is less than or equal to the boundary value, while each element in the right part is greater than or equal to the boundary value.

(3) then, the left and right data can be sorted independently. For the array data on the left, you can take another demarcation value and divide the data into two parts, left and right, with a smaller value on the left and a larger value on the right. The array data on the right can be treated similarly.

(4) by repeating the above process, we can see that this is a recursive definition. The left part is sorted recursively, and then the right part is arranged recursively. When the sorting of the data in the left and right parts is completed, the sorting of the whole array is completed.

The idea can be summarized as follows: digging holes and filling numbers + divide and conquer method.

For example, the following diagram:

The figure above is based on the value of the last element.

Those smaller than the benchmark are on the left, and those larger than the benchmark are on the right.

Then repeat the above with divided parts until there is only one data in each part.

Train of thought analysis

The basic idea is like the above, but there are many ways to realize it. Generally, the reference value is taken from the beginning to the end or in the middle. Here, the middle of the array is used as the reference value to explain.

Raw array: arr = [- 9, 78, 0, 23, 567-70]

Set two variables, left subscript L = 0, right subscript R = array size-1, the value in the middle of the selected array is the base value, pivot = arr [(L + R) / 2], the base value is 0. Then use two variables to save the left subscript and the right subscript, left = L and right = R, in preparation for subsequent sorting.

As you can see, pivot divides the array into two groups

The group on the left, from left to right, compares with the benchmark value one by one, finds out the value that is larger than the benchmark value, and jumps out of the search cycle.

The group on the right, from right to left, compares with the benchmark value one by one, finds out the value that is smaller than the benchmark value, and jumps out of the search cycle.

You can see that the left and right groups each find a corresponding value, so let them exchange it.

Then keep looking until the left and right sides meet

You can see that the group on the left is done, and L points to the benchmark, so jump out of the search cycle and start looking for the group on the right.

But we can see that the numbers on the right also follow the rules, so R loops through to the base value, and L and R have already hit each other, and this round is over. This round is called quick sort.

Continue the above quick sort operation for the separated groups until there is only one number left in the group, and the sorting is complete.

Take a step forward and a step backward for L and R respectively

As shown in the figure, you can use these two variables again to quickly sort the two groups.

Quickly sort the groups on the left first, and do the same thing above

Here we use the left and right saved in the last fast loop (the image above is not drawn).

Because left points directly to pivot here, there is no need to do a mobile search. R is compared with pivot.

< -9 ，R和left进行交换，得到如下图，注：pivot 是一个值,不是引用类型 因为 R 和 left 没有碰头，所以还得进行一次循环比较。因为 R 就在基准点这，所以不移动，R 和pivot 比较，-9 >

-567. so left takes a step forward.

At this point, R and left have run into each other, and this round is over.

The same is true for the group on the right, so there won't be too much analysis here.

L-pivot-r group from left to right, one group from right to left

As you can see, after grouping, you can use recursion to continue grouping this group, and then quickly sort them.

Code implementation derivation implementation

The derivation method realizes the first round first.

@ Test public void processDemo () {int arr [] = {- 9,78,0,23,-567,70}; System.out.println ("primitive array:" + Arrays.toString (arr)); processQuickSort (arr, 0, arr.length-1) } / * * @ param arr * @ param left the starting point of the subscript on the left, to the middle value is the end point of the subscript on the right side of a set of * @ param right, and to the middle value, it is a set of * / public void processQuickSort (int [] arr, int left, int right) {/ * basic idea: choose a base value and divide the base value into a group. Those larger than the benchmark are divided into a group. The realization idea here is: 1. The selected benchmark value is the value 2 in the middle of the array. The median divides the array into two groups of 3. The group on the left, from left to right, compares it with the benchmark value one by one, and finds a value that is 4. 5% higher than the benchmark value. The group on the right, from right to left, compares it with the benchmark value one by one to find a value that is less than the benchmark value of 5. 5. If you find a value on the left and right, let the two values be swapped for 6. Then keep looking until the left and right sides meet, and this round is over. This round is called Quick sort 7. Continue to perform the above quick sort operation on the separated groups until there is only one number left in the group, then the sorting completes l-pivot-r group from left to right, one group from right to left, * / int l = left; int r = right / / Center point, let this point be the benchmark value int pivot = arr [(left + right) / 2]; / / when they don't encounter it, you can continue to look for while (l) in this round.

< r) { // 左边组：当找到大于基准值时，退出循环，则表示该值需要交换到右侧去: arr[l] >

Pivot / / that is, if arr [l]

< pivot，则表示还没有找到比基准值大的数 // 注意：不能等于 pivort，因为最差的情况没有找到，则最后 arr[l] 就是 pivot 这个值，也同样退出循环 while (arr[l] < pivot) { l++; // 所以让左边这一组继续找 } // 右边组：当找到小于基准值时，退出循环，则表示该值需要交换到左侧去：arr[r] < pivot // 也就是说，如果 arr[l] >

Pivot, it means that a number less than the benchmark value has not been found / / Note: it is also the same as above, it cannot be equal to pivort while (arr [r] > pivot) {rmuri- / / Let the right group continue to look for} / / when the left side and the right side collide, it means that neither side is found. This round does not need to be exchanged / equals to indicate that the middle subscript if (l > = r) {break;} / / is found. When found, the two numbers are exchanged. / / Note: there may be a group that has been found or not found, but the other group has been found, so one points to pivot and / / the other points to the number to be exchanged. After the exchange, the position of the pivot value in the array will change, and the next exchange method will change. This place needs to think about it. Int temp = arr [l]; arr [l] = arr [r]; arr [r] = temp / / after the exchange, / / when the array is: {- 9, 78, 0,-23, 0, 70} (there are multiple values of pivot in the array), you can verify the logic here / / if there is no such decision, it will cause l to be always less than r. If the loop cannot be pulled out, the if (arr [l] = = pivot) {/ * l cannot move forward by itself. Because when the exchange is completed, it is: {- 9, 0, 0,-23, 78, 70} l = 1dint arr [l] = 0r = 4je ar [r] = 78 after another cycle, l = 1je arr [l] = 0r = 3 Arr [r] =-23 the array after exchange is: {- 9 At this time l = 1 ~ (st) ~ arr [l] =-23 R = 3 and after another cycle, l = 2 and 0, the array is: {- 9 ~ (th) ~. 70} into the endless cycle here, use your head and think about why you are using rMurray 1 here. Because the condition in if is arr [l] = pivot, if there are no multiple values equal to the benchmark value in the array to be sorted, then l will run across the dividing line (benchmark value) and go to another group, and the algorithm will fail. Another reason is that r has just been exchanged and must be larger than the benchmark value. So there is no need to compare with the benchmark value * / r-= 1. } / / this is the same as the above. If we first go to the above rsway 1 / / and meet here (that is to say, there are multiple values equal to the benchmark value), then the next time we will have the same two values, one is r = = one is the base value / / but they are the same value, r is one step back and one step forward, it does not affect. But when you go through this logic again, it will cause l > r to exit the entire loop if (arr [r] = = pivot) {l + = 1;} System.out.println ("after the first round:" + Arrays.toString (arr));}

Note: the above algorithm, especially the boundary determination, is a bit difficult to understand when determining the boundary of rmuri after exchange, but it is important to understand why it is written in this way.

Test information output

Original array: [- 9, 78, 0, 23,-567, 70]

After the first round of sorting: [- 9,-567,0,23,78,70]

So how do you recurse to the left and right? The code above is followed by the following implementation

System.out.println ("after the 1st round:" + Arrays.toString (arr)); / * if (l > = r) {break } loop will jump out of this code, l = r * / / if l = r, there will be an endless loop, stack overflow / / think about if (l = = r) {lumped; rink- } / / start the left recursion / / the above algorithm is rmurmurine left +, go to the middle of the two groups, when the

< r 时，表示还可以继续分组 if (left < r) { processQuickSort(arr, left, r); } if (right >

L) {processQuickSort (arr, l, right);} complete implementation

In fact, the complete realization and deduction realization is almost enough. In order to deepen the memory, I analyze and dictation according to the basic ideas and ideas.

/ * Quick sort dictation implementation * * basic idea: through a trip, the data to be sorted is divided into two independent parts, and all the data in one part is smaller than all the data in the other part. * thought analysis: * {- 9,78,0,23,-567,70}; length=6 * 1. Select the middle value as the benchmark value: (0 + (6-1)) / 2 = [2] = 0 * 2. In the left section on the left, from 0 to the median value-1: 0, 1:-9, 78, find a number * 3 that is larger than the base value. In the right section on the right, from the middle value + 1 to the array size-1, 3, 7, 5, 5, and 23, find a number that is smaller than the base value, * 4. If found, swap them, so that a quick sort is completed: all the data in one part is smaller than all the data in the other part. * 4. If the left part can still be grouped, make a left recursive call to * 5. If the right part can also be grouped Then make a right recursive call * * to put it simply: the schematic diagram of a quick sort round is as follows: * the benchmark value in the middle * l-pivot-r * A group from left to right, a group from right to left. * find a number that is larger than the benchmark value and find a number that is smaller than the benchmark value * and then exchange * / @ Test public void quickSortTest () {int arr [] = {- 9 78, 0, 23,-567,70} / / int arr [] = {- 9, 78, 0,-23, 0, 70}; / / an array that will result in a swap exception during derivation, int left = 0; int right = arr.length-1; System.out.println ("primitive array:" + Arrays.toString (arr)); quickSort (arr, left, right) System.out.println ("after sorting:" + Arrays.toString (arr));} public void quickSort (int [] arr, int left, int right) {/ / find the intermediate value int pivotIndex = (left + right) / 2; int pivot = arr [pivotIndex]; intl = left; int r = right; while (l

< r) { // 从左往右找，直到找到一个数，比基准值大的数 while (arr[l] < pivot) { l++; } // 从右往左找，知道找到一个数，比基准值小的数 while (arr[r] >

Pivot) {r muri;} / indicates that if (l > = r) {break;} / / was not found for exchange int temp = arr [l]; arr [l] = arr [r]; arr [r] = temp / / then in the next round, the value on the left will no longer participate in the sort, because it has just been exchanged, it must be lower than the benchmark value / / then in the next round, the value on the right will no longer participate in the sort, because it must be larger than the benchmark value in the next round. } / / when the middle value is not found after a round of search, / / they need to pass by, that is, they are re-grouped, and the median value no longer participates in the grouping / / otherwise, in some cases, it will enter the endless cycle if (l = = r) {lumped; rmurf- } / / if you can continue grouping on the left, then continue to if / / pass by due to brush, then the group value on the left is the first one before the initial start and the intermediate value, which is the r if (group value) obtained here.

< r) { quickSort(arr, left, r); } if (right >

L) {quickSort (arr, l, right);}}

In addition, in the process of implementation, we sort out why some code should judge the boundary in that way. You will find that there is one difference between the above code and the derived code. This is my own logical improvement, which is easier to understand. At present, no bug has been found. If there is anything wrong, please comment and point out, after all, this algorithm is still a bit difficult.

Large amount of data time-consuming test / * large data sorting time test * / @ Test public void bulkDataSort () {int max = 80000 beat / int max = 8; int [] arr = new int [max]; for (int I = 0; I

< max; i++) { arr[i] = (int) (Math.random() * 80000); } if (arr.length < 10) { System.out.println("原始数组：" + Arrays.toString(arr)); } Instant startTime = Instant.now();// processQuickSort(arr, 0, arr.length - 1); // 和老师的原版代码对比，结果是一样的 quickSort(arr, 0, arr.length - 1); if (arr.length < 10) { System.out.println("排序后：" + Arrays.toString(arr)); } Instant endTime = Instant.now(); System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒"); } 多次运行输出 共耗时：40 毫秒 共耗时：52 毫秒 共耗时：36 毫秒 共耗时：31 毫秒 性能分析 快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。 理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。 为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用"三者值取中"方法，即比较H->

R [low] .key, H-> r [high] .key and H-> r [(low+high) / 2] .key, and the element whose keyword is the median is the middle number.

It can be proved that the average time complexity of quick sorting is also O (nlog2n). Therefore, this sorting method is considered to be the best internal sorting method at present.

From the perspective of spatial performance, although quick sorting only needs the auxiliary space of one element, quick sorting needs a stack space to achieve recursion. At best, each sort of quick sort splits the sequence of elements evenly into two child tables of similar length, with a maximum stack depth of log2 (n = 1), but in the worst case, the maximum stack depth is n. In this way, the space complexity of quick sort is O (log2n).

The above is all the contents of the article "sample Analysis of Quick sorting of java sorting algorithm". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, 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.