Optimization strategy for implementing quick sort algorithm in Java

Title: Efficient method and code example to implement quick sort algorithm in Java

Introduction:
Quick sort is an efficient sorting algorithm based on divide and conquer The idea is to have better performance under average circumstances. This article will introduce the implementation process of the quick sort algorithm in detail through Java code examples, along with performance optimization tips to improve its efficiency.

1. Algorithm principle:
The core idea of ​​quick sorting is to select a benchmark element and divide the sequence to be sorted into two subsequences through one sorting pass. The elements of one subsequence are smaller than the benchmark element. Small, the elements of the other subsequence are larger than the base element, and then the two subsequences are sorted recursively.

2. Java code implementation:
The following is a sample code for implementing the quick sort algorithm in Java language:

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left + 1;
        int j = right;

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

            if (i > j) {
                break;
            }

            swap(arr, i, j);
        }

        swap(arr, left, j);
        return j;
    }

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

3. Performance optimization:

1. Random Select the basis element: In order to avoid the time complexity of quick sort degenerating into O(n^2) in some specific cases in actual operation, the basis element can be randomly selected instead of always selecting the first element or the last element of the sequence. element.
2. Optimize exchange operations: In the partition method, when exchanging elements, you can first determine whether the elements are equal to avoid unnecessary exchange operations to improve performance.
3. Adopt insertion sort for small-scale sequences: For small-scale sequences, the recursive overhead of quick sort may exceed the overhead of direct insertion sort, so the smaller-scale sequences can be sorted after a certain level of recursion. Implemented using insertion sort algorithm.

public class QuickSort {
    private static final int INSERTION_SORT_THRESHOLD = 7;

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            if (right - left <= INSERTION_SORT_THRESHOLD) {
                insertionSort(arr, left, right);
            } else {
                int pivotIndex = randomizedPartition(arr, left, right);
                quickSort(arr, left, pivotIndex - 1);
                quickSort(arr, pivotIndex + 1, right);
            }
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left + 1;
        int j = right;

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

            if (i > j) {
                break;
            }

            swap(arr, i, j);
        }

        swap(arr, left, j);
        return j;
    }

    private static int randomizedPartition(int[] arr, int left, int right) {
        int pivotIndex = (int) (Math.random() * (right - left + 1)) + left;
        swap(arr, left, pivotIndex);
        return partition(arr, left, right);
    }

    private static void swap(int[] arr, int i, int j) {
        if (i != j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }
}

4. Summary:
This article shows the basic implementation and performance optimization techniques of the quick sort algorithm based on Java language. When processing large-scale data sets, optimization methods such as selecting random reference elements and using insertion sort for small-scale sequences can improve algorithm performance. By understanding the principles and implementation details of quick sort, we can use this algorithm for efficient sorting in practical applications.

The above is the detailed content of Optimization strategy for implementing quick sort algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!