Detailed explanation of QuickSort algorithm: an efficient sorting tool

QuickSort is an efficient sorting algorithm based on the divide-and-conquer strategy. The divide-and-conquer method decomposes the problem into smaller sub-problems, solves these sub-problems separately, and then combines the solutions of the sub-problems to obtain the final solution. In quick sort, an array is divided by selecting a partition element, which determines the split point of the array. Before partitioning, the position of the partitioning element is rearranged so that it is before the element that is larger than it and after the element that is smaller than it. The left and right subarrays will be divided recursively in this manner until each subarray contains only one element, at which point the array is sorted.

How quick sort works

Let us sort the following array in ascending order as an example:

Step 1: Select the pivot element

We choose the last element as the pivot:

Step 2: Rearrange pivot elements

We place the pivot element before elements that are larger than it and after elements that are smaller than it. To do this, we will iterate through the array and compare the pivot to each element before it. If an element larger than the pivot is found, we create a second pointer for it:

If an element smaller than the pivot is found, we swap it with the second pointer:

Repeat this process, setting the next element larger than the pivot to the second pointer, swapping if an element smaller than the pivot is found:

Continue this process until you reach the end of the array:

After completing the element comparison, the element smaller than the pivot has been moved to the right, then we swap the pivot with the second pointer:

Step 3: Divide the array

Divide the array according to the partition index. If we represent the array as arr[start..end], then by dividing the array by partition, we can get the left subarray arr[start..partitionIndex-1] and the right subarray arr[partitionIndex 1..end].

Continue dividing the subarrays in this way until each subarray contains only one element:

At this point, the array is sorted.

Quick sort code implementation

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 將最后一個元素設置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動到樞軸左側
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個指針交換
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分區(qū)索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分區(qū)索引
            int partitionIndex = partition(arr, start, end);
            // 遞歸調(diào)用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

Code interpretation

quickSort method: First call the partition method to divide the array into two sub-arrays, and then call quickSort recursively to sort the left and right sub-arrays. This process continues until all subarrays contain exactly one element, at which point the array is sorted.

partition Method: Responsible for dividing the array into two sub-arrays. It first sets the pivot and the pointer to the next larger element, then iterates through the array, moving elements smaller than the pivot to the left. After that it swaps the pivot with the second pointer and returns the partition position.

Run the above code, the console will output the following:

Unsorted array: [8, 6, 2, 3, 9, 4] Sorted array: [2, 3, 4, 6, 8, 9]

Time complexity

Best case (O(n log n)): The best case occurs when the pivot splits the array into two nearly equal parts every time.

Average case (O(n log n)): In the average case, the pivot splits the array into two unequal parts, but the recursion depth and number of comparisons are still proportional to n log n.

Worst case (O(n2)): The worst case occurs when the pivot always splits the array into very unequal parts (e.g. one part has only one element and the other has n-1 elements) . This can happen, for example, when sorting an array in reverse order, and the pivot is chosen poorly.

Space complexity (O(log n)): Quick sort is usually implemented in-place and does not require additional arrays.

The above is the detailed content of Understanding Quick Sort Algorithm (with Examples in Java). For more information, please follow other related articles on the PHP Chinese website!