Detailed step-by-step analysis of implementing quick sort algorithm in Java

Detailed step-by-step analysis of implementing quick sort algorithm in Java

Quick Sort is an efficient sorting algorithm that uses the idea of ​​divide and conquer. The sequence to be sorted is divided into smaller subsequences, then the subsequences are sorted, and finally the subsequences are merged to obtain an ordered sequence. This article will introduce the steps of the quick sort algorithm in detail and provide specific Java code examples.

1. Algorithm steps:

The basic steps of the quick sort algorithm are as follows:

1.1 Select an element as the pivot (pivot), which can be the first one element, the last element, or a randomly selected element.

1.2 Divide the sequence to be sorted into two subsequences: a sequence of elements less than or equal to the benchmark and a sequence of elements greater than the benchmark.

1.3 Recursively apply the quick sort algorithm to two subsequences.

1.4 Merge subsequences to obtain a complete ordered sequence.

2. Java code example:

The following is a specific code example using Java to implement the quick sort algorithm:

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0 || low >= high) {
            return;
        }

        // 选择基准元素
        int pivotIndex = partition(arr, low, high);

        // 对基准元素左边的子序列递归排序
        quickSort(arr, low, pivotIndex - 1);

        // 对基准元素右边的子序列递归排序
        quickSort(arr, pivotIndex + 1, high);
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择最后一个元素作为基准
        int pivot = arr[high];

        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);

        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 6, 3, 8, 4, 7};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("排序后的结果：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

3. Example description:

In the above code, we define a quickSort method for sorting the sequence to be sorted, and the partition method for dividing the sequence into two subsequences.

In the quickSort method, first determine whether the sequence needs to be sorted, then select the base element, and call the partition method to divide the sequence. Next, the quickSort method is recursively applied to the two subsequences until the sequence length is 1. The

partition method selects the last element as the baseline and uses the variable i to record the number of elements that are less than or equal to the baseline. By traversing the sequence, if the element is less than or equal to the reference, it is exchanged with the position pointed to by i, and finally the reference element is placed in the appropriate position.

Finally, run the main function to output the sorted results.

The time complexity of the quick sort algorithm is O(nlogn) and has high efficiency. By correctly understanding and applying the above steps, the quick sort algorithm can be flexibly applied in actual programming to achieve sorting requirements.

The above is the detailed content of Detailed step-by-step analysis of implementing quick sort algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!