Analyze the time complexity and space complexity of Java quick sort algorithm

Time complexity and space complexity analysis of Java quick sort function

Quick Sort (Quick Sort) is a comparison-based sorting algorithm, which uses The array is divided into two subarrays, and then the two subarrays are sorted separately until the entire array is sorted. The time complexity and space complexity of quick sort are key factors that we need to consider when using this sorting algorithm.

The basic idea of ​​quick sort is to select an element as the pivot (pivot), and then divide other elements in the array into two sub-arrays based on their relationship with the pivot. The elements of one sub-array are less than or equal to the pivot. element, the elements of the other sub-array are all greater than or equal to the pivot element. The two subarrays are then sorted recursively and finally merged.

The following is a code example of a quick sort function implemented in Java:

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[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 = {6, 5, 3, 1, 8, 7, 2, 4};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

The time complexity of quick sort is O(nlogn), where n is the length of the array. In the best case, where each partition divides the array exactly equally, the time complexity of quick sort is O(nlogn). In the worst case, that is, each partition finds the smallest or largest element of the array as the pivot element, the time complexity of quick sort is O(n^2). On average, the time complexity of quick sort is also O(nlogn).

The space complexity of quick sort is O(logn), where logn is the depth of the recursive call stack. In the best case, where each partition divides the array exactly equally, the space complexity of quick sort is O(logn). In the worst case, that is, each partition finds the smallest or largest element of the array as the pivot element, the space complexity of quick sort is O(n). On average, the space complexity of quicksort is also O(logn).

It should be noted that the space complexity of quick sort refers to the additional space required in addition to the input array, and does not include the space of the input array.

To sum up, quick sort is an efficient sorting algorithm with low time complexity and space complexity. In practical applications, although the worst-case time complexity of quick sort is O(n^2), the average time complexity of quick sort is O(nlogn), and the data in practical applications is very small. The worst-case scenario is less likely, so quick sort is still a selection sort algorithm.

The above is the detailed content of Analyze the time complexity and space complexity of Java quick sort algorithm. For more information, please follow other related articles on the PHP Chinese website!