Detailed code and popular explanation of Java quick sorting

Basic concepts of quick sorting:

The core of quick sorting is to choose oneReference value, and then divide the array into two parts:

left: Elements smaller than the benchmark value.
right: Elements with larger than the benchmark value. Then continue this process recursively on the left and right parts until each part is sorted.

Come on, let’s use real-life examples to understand!

Suppose you are sorting out a bunch of digital cards 📇, you want to arrange these cards in order from small to large. Quick sort is like you stand by a table, do a big sorting of these cards, and then constantly divide the small and large cards into left and right sides until they are both arranged in place.

Let's give a specific example:

You have a bunch of numbers like this:
[8, 3, 5, 1, 9, 6]

Step 1: Select a benchmark value (pivot)

We choose a number from the middle as the reference value, such as select6As a benchmark.

Step 2: Sorting

Smaller than 6Put the number inleft,Right now:[3, 5, 1]
Greater than 6Put the number inright,Right now:[8, 9]
Reference value6Just put it in the middle.

Now we have such sorting results:Left: [3, 5, 1], Middle: 6, Right: [8, 9]

Step 3: Recursively process the left and right sides

Quick sort of the array on the left [3, 5, 1] again：
- Select the baseline value:3
- Left: [1] (smaller than 3)
- Right: [5] (larger than 3)
Now the left is lined up:[1, 3, 5]
Array on the right [8, 9]：
- This part has been arranged because 8 is smaller than 9.

Step 4: Combination results

Now we combine all the parts:

left：[1, 3, 5]
Reference value：6
right：[8, 9]

The final sorting result is:
[1, 3, 5, 6, 8, 9]

A brief summary of the steps to quickly sort:

Select a reference value: Select a number as the reference value, usually select an element in the array.
Sorting: Put the ones smaller than the reference value to the left and the ones larger than the reference value to the right.
recursion: Continue the same operation on the left and right parts.
Combination results: Finally put the sorted parts together.

Use life examples to understand:

Imagine You have to organize the socks in a large drawer 🧦. You first pick out one as a "basic sock", such as a medium length, and then start organizing:

Put it aside shorter than the benchmark socks (left).
Place the other side (right) longer than the benchmark stockings.

Then you organize the socks on both sides separately and continue sorting in the same way until all the socks are arranged in order according to their lengths!

Advantages of Quick Sorting

Quick sorting is efficient because it cuts the size of the problem in half every time. By breaking the problem down into small problems, it can quickly solve the sorting problem. The average time complexity isO(n log n), in most cases much faster than bubble sorting (time complexity O(n²)).

Quickly sorted full Java code:

public class QuickSortExample {

    // The main method of quick sorting, passing in array, minimum index and maximum index    public static void quickSort(int[] arr, int low, int high) {
        // If the low index is smaller than the high index, it means that the array has not been sorted yet        if (low &lt; high) {
            // Find the location of the base element and divide the array into two parts            int pivotIndex = partition(arr, low, high);
            
            // Quickly sort the left part of the benchmark recursively            quickSort(arr, low, pivotIndex - 1);
            // Quickly sort the right part of the benchmark recursively            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Partition method: select a reference value, place elements smaller than the reference to the left, and those larger than the reference to the right    private static int partition(int[] arr, int low, int high) {
        // Select the rightmost element as the reference        int pivot = arr[high];
        
        // i is used to track the position of an element smaller than the reference value        int i = low - 1; 

        // Iterate through the array and find all elements smaller than the reference value        for (int j = low; j &lt; high; j++) {
            // If the current element is less than or equal to the reference value            if (arr[j] &lt;= pivot) {
                i++; // Add i to prepare to swap the position of small elements                
                // Exchange arr[i] and arr[j] and put small elements in front                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Finally, put the reference value in the correct position (middle)        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // Return to the correct position of the reference value        return i + 1;
    }

    // Test the main function of the quick sort method    public static void main(String[] args) {
        // Define an array that needs to be sorted        int[] arr = {8, 3, 5, 1, 9, 6};

        // Print the array before sorting        ("Array before sorting:");
        printArray(arr);

        // Call the quick sort method to sort the entire array        quickSort(arr, 0,  - 1);

        // Print the sorted array        ("Sorted array:");
        printArray(arr);
    }

    // Helper method: Print all elements in the array    private static void printArray(int[] arr) {
        for (int num : arr) {
            (num + " ");
        }
        ();
    }
}

Detailed code explanation:

quickSortMethod: This is the main method for quick sorting. It receives an array, a minimum index (low) and a maximum index (high). If the size of the current subarray is greater than 1 (low < high), it will find the correct position of the benchmark value and then recursively sort the left and right parts.
partitionMethod: The function of this method isDivide the array into two parts：
- On the left are elements smaller or equal to the benchmark value.
- On the right is an element that is larger than the benchmark value.
  It returns where the reference value ends up, so we know where to split the array into two.
printArrayMethod: This method is aAuxiliary methods, used to print the array content, so that we can view the effect before and after sorting.

A popular version of this example:

Select the reference value：
For example, we start from an array[8, 3, 5, 1, 9, 6]Selected6As the reference value. This benchmark value is like a "dividing line", we need to make it less than6Put the element on the left and put it greater than6Place the element on the right.
Left or so：
Iterate through the array, and then it will be less than6The element of is placed in front of the array, greater than6Put the element of behind the array. for example3, 5, and1Will be moved to the front,8, 9Will be placed behind,6As the reference value, it is in the middle.
Recursive processing：
Then we go to the left part[3, 5, 1]and the right part[8, 9]Continue to do the same sorting until there is only one element in each section.
Sorting is complete：
Finally, all the elements are arranged in order from small to large, and the result is[1, 3, 5, 6, 8, 9]。

Array before sorting:
8 3 5 1 9 6
Sort array:
1 3 5 6 8 9

summary:

Quick sorting is done by picking a benchmark value and then dividing the array into two parts: the left side is smaller than the benchmark and the right side is larger than the benchmark.
Then continue to recursively sort the left and right parts quickly until the array is sorted.
The whole process is actually constantly "sorting" elements, similar to how you quickly sort items of different sizes and finally get the sorting results.

Summarize

This is all about this article about Java Quick Sorting Implementation. For more related Java Quick Sorting Implementation Content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!