Strategies and techniques to improve the efficiency of Java quick sort function

Methods and techniques for optimizing Java quick sort function

Quicksort (Quicksort) is a common sorting algorithm. The idea is to divide the array into smaller ones. and the two larger sub-arrays to achieve sorting, and then sort the sub-arrays again to achieve overall ordering. In practical applications, we need to optimize the performance of the quick sort function to improve the efficiency of sorting. The following will introduce some methods and techniques for optimizing the quick sort function, and give specific code examples.

1. Random selection of reference elements
   The selection of reference elements in quick sort has an important impact on the efficiency of sorting. The traditional approach is to select the first or last element as the base element. However, if the array is already sorted or approximately sorted, this selection method may cause the time complexity of quicksort to degenerate to O(n^2). In order to avoid this situation, we can randomly select an element as the reference element, which can break the order of the input data to a certain extent and improve performance.

The following is a code example for randomly selecting reference elements:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = randomPartition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int randomPartition(int[] arr, int low, int high) {
        int randomIndex = ThreadLocalRandom.current().nextInt(low, high + 1);
        swap(arr, randomIndex, high);
        return partition(arr, low, high);
    }

    public 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;
    }

    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, 9, 1, 3, 7, 6};
        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }
}

2. Three sampling partition
   In the traditional quick sort algorithm, a single reference element is used to divide the array. However, when there are a large number of duplicate elements in the array, such a division will cause the time complexity of quick sort to degrade to O(n^2). In order to solve this problem, we can use the Median-Of-Three Partitioning method to be more flexible in the selection of reference elements.

The basic idea of ​​three-sampling division is to select three elements in the array (such as the first, last and middle elements), and then use their median as the reference element. By using such a partitioning method, we can try to avoid the performance degradation problem of quick sort when dealing with a large number of repeated elements.

The following is a code example using three-sampling partitioning:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int[] pivotIndices = medianOfThree(arr, low, high);
            int left = pivotIndices[0];
            int right = pivotIndices[1];
            quickSort(arr, low, left - 1);
            quickSort(arr, left + 1, right - 1);
            quickSort(arr, right + 1, high);
        }
    }

    public static int[] medianOfThree(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (arr[high] < arr[low]) {
            swap(arr, low, high);
        }
        if (arr[mid] < arr[low]) {
            swap(arr, low, mid);
        }
        if (arr[high] < arr[mid]) {
            swap(arr, mid, high);
        }
        swap(arr, mid, high - 1);
        return partition(arr, low + 1, high - 1);
    }

    public static int[] partition(int[] arr, int low, int high) {
        int left = low;
        int right = high;
        int pivot = arr[high];
        int i = low - 1;
        while (true) {
            while (arr[++i] < pivot) {
            }
            while (left < right && pivot < arr[--right]) {
            }
            if (left >= right) {
                break;
            }
            swap(arr, left, right);
        }
        swap(arr, left, high);
        return new int[]{left, right};
    }

    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, 9, 1, 3, 7, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

By randomly selecting the basis elements and using the three-sampling partitioning method, we can optimize the performance of the Java quick sort function. These methods can improve the efficiency of sorting algorithms when dealing with different data distributions and avoid the degradation of time complexity.

The above is the detailed content of Strategies and techniques to improve the efficiency of Java quick sort function. For more information, please follow other related articles on the PHP Chinese website!