Quickly master java sorting algorithm - quick sort (picture and text)

Concept

Quick sorting is an exchange sort. The main step is to use the reference element for comparison, and sort the elements that are smaller than the reference element. The ones that are larger than the base element move to one side, and the ones that are larger than the base element move to the other side. Thus, the array is divided into two parts, and then the reference elements are selected from the two parts and the above steps are repeated. The process is as follows:

(Recommended video: java video tutorial)

Purple: base element
Green: greater than base element
Yellow: less than Baseline elements

#This idea is called divide and conquer.

Basic elements

The selection of datum elements can be randomly selected. In the following use, I will use the first element as the base element.

Sort process

The sorting and splitting process is as shown below:

Purple is the base element, (re-selected in each round)
Green is other elements

First round

Second round

Third round

As shown in the figure above:

If the number of elements is n, because the sorting process needs to be compared with all elements, the time complexity is O(n),
On average, sorting rounds require logn rounds, so the average time complexity of quick sort is O(nlogn).

The implementation method of sorting

The implementation methods include bilateral circulation method and unilateral circulation method

Bilateral circulation method

The first choice is to select the pivot element (pivot) 4, and set the pointers left and right to point to the leftmost and rightmost elements of the array, as follows:

First In this loop, first start with the data pointed to by the right pointer (rightData) and compare it with the base element.
If rightData >= pivot, the right pointer moves to the left. If rightData The data pointed by the left pointer (leftData) is compared with the reference element. If leftData pivot, the elements pointed to by left and right are exchanged.

After the first round of pointer movement, the following structure is obtained:

Then the elements pointed to by left and right are exchanged:

The first round of loop ends, switch to the right pointer again, and repeat the above steps.

After the second cycle, we get:

After the third round, we get:

After the fourth cycle, we get:

It is judged that the left and right pointers point to the same element, the pointers stop moving, and the pivot and pointer elements are exchanged, we get:

Declares the end of the cycle and divides it into two parts according to the Pivot element. The arrays of these two parts are then operated according to the above steps.

Implementation code

public class DoubleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left = pivot) {
                right--;
            }

            // 控制left指针比较并右移
            while (left <p id="单边循环法" style="white-space: normal;"><strong>Unilateral loop method</strong></p><p>Bilateral loop method compares and exchanges elements from both sides of the array, and The one-sided loop rule traverses from one side of the array and compares and exchanges backwards, making it easier to implement. <br>The process is as follows: </p><blockquote><p>Firstly, the pivot element is selected (can be selected randomly) <br>Set a mark pointer to point to the starting position of the array, representing the area boundary that is smaller than the baseline element (don’t understand Just understand it as being used to exchange elements later) </p></blockquote><p>The original array is as follows: </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/b739c5c8ed7df91b0c77a8fae57a6150-11.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Quickly master java sorting algorithm - quick sort (picture and text)"></p><blockquote><p>从基准元素下一位开始遍历数组<br>如果该元素大于基准元素，继续往下遍历<br>如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。</p></blockquote><p>遍历到元素3时，因为3 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-12.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Quickly master java sorting algorithm - quick sort (picture and text)"></p><p>然后交换元素</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-13.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Quickly master java sorting algorithm - quick sort (picture and text)"></p><p>然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。</p><p id="实现代码-1"   style="max-width:90%"><strong>实现代码</strong></p><pre class="brush:php;toolbar:false">public class SingleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 分治（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int mark = startIndex;

        for(int i = startIndex + 1; i<p id="总结" style="white-space: normal;"><strong>总结</strong></p><p>本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。</p><p>参考资料：《小灰的算法之旅》 第四章。</p><p>本文来自php中文网，<a href="https://www.php.cn/java/base/" target="_blank">java教程</a>栏目，欢迎学习！  </p>

The above is the detailed content of Quickly master java sorting algorithm - quick sort (picture and text). For more information, please follow other related articles on the PHP Chinese website!