Optimization and implementation principles: Quick sort in Java

Implementation principles and optimization of Java quick sort function

Quick sort is an efficient sorting algorithm. Its implementation idea is to divide a big problem into Divide the problem into multiple small problems, solve the sub-problems recursively, and finally obtain the overall solution. In quick sort, we need to select a benchmark element and divide the array into two parts, one part is smaller than the benchmark element, and the other part is larger than the benchmark element. The two parts are then quickly sorted again until there is only one element per subproblem. Finally, the solutions to all subproblems are combined to obtain the ordered sequence of the array.

The specific implementation process is as follows:

1. Select a benchmark element. There are many ways to select the base element. A common method is to select the first element of the array.

2. Divide the array. Divide an array into two parts by comparing the size of the elements in the array to the base element. One part contains elements smaller than the base element, and one part contains elements larger than the base element.

3. Recursive sorting. Sort the two divided subarrays recursively until the subarrays contain only one element.

4. Merge subarrays. Combine the sorted subarrays to get the final sorted array.

The following is an example of Java code:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high); // 获取划分点
            quickSort(arr, low, partitionIndex - 1); // 对左侧子数组进行快速排序
            quickSort(arr, partitionIndex + 1, high); // 对右侧子数组进行快速排序
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选取第一个元素作为基准元素
        int i = low + 1; // 左指针
        int j = high; // 右指针

        while (i <= j) {
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, low, j); // 将基准元素放到正确的位置

        return j;
    }

    public 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, 6, 1, 3, 9, 4, 8, 7};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Through the above example code, we can clearly see the implementation principle of the quick sort function. In this example, we use the base element selection method to select the first element of the array. The quick sort function accepts three parameters: an array, a left boundary, and a right boundary. By calling the quickSort function recursively, the array is divided and sorted, and the sorted result is finally output.

Although the quick sort algorithm is already very efficient, we can also perform some optimizations on it to further improve performance:

1. Randomly select the benchmark element: Select the benchmark element in the first step When , instead of selecting the first element fixedly, an element is randomly selected. Doing so reduces the probability of the worst case scenario and improves the average performance of the algorithm.
2. Method of three numbers: When selecting the reference element, not only random selection can be used, but also the method of three numbers can be used. That is, select the element with the middle value from the left, middle, and right positions as the base element. This further reduces the probability of the worst-case scenario occurring.
3. Switch to insertion sort: When the size of the subarray is small enough, you can switch to the insertion sort algorithm. Because insertion sort is faster for small-scale array sorting and is simpler to implement.

The above is an introduction to the implementation principle and optimization of Java quick sort function. By understanding and optimizing the quick sort algorithm, the sorting efficiency of the program can be improved, making the sorting process faster and more efficient.

The above is the detailed content of Optimization and implementation principles: Quick sort in Java. For more information, please follow other related articles on the PHP Chinese website!