Quick sort algorithm implemented in Java and its efficiency evaluation

Java implementation of quick sort and its performance analysis

Quick Sort (Quick Sort) is a very commonly used and efficient sorting algorithm. It is a divide and conquer method. The thought of Divide and Conquer. This algorithm divides an array into two sub-arrays, then sorts the two sub-arrays respectively, and finally turns the entire array into an ordered sequence. Quick sort shows excellent performance when processing large-scale data.

Quick sorting is implemented in a recursive way. The basic idea is as follows:

1. Select a reference element (pivot) and divide the array into two sub-arrays. The one larger than the reference element is placed on the right. , elements smaller than the reference element are placed on the left;
2. Quickly sort the left and right subarrays recursively;
3. When the length of the subarray is 1 or 0, stop the recursion and the sorting is completed.

The following is a code example of using Java language to implement quick sort:

public class QuickSort {
    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivotIndex = partition(arr, start, end); // 将数组分成两部分，并返回基准元素的索引
            quickSort(arr, start, pivotIndex - 1); // 对左子数组进行快速排序
            quickSort(arr, pivotIndex + 1, end); // 对右子数组进行快速排序
        }
    }

    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[start]; // 选择数组的第一个元素作为基准元素
        int left = start + 1;
        int right = end;
        while (left <= right) {
            // 从左边找到大于基准元素的值
            while (left <= right && arr[left] <= pivot) {
                left++;
            }
            // 从右边找到小于基准元素的值
            while (left <= right && arr[right] > pivot) {
                right--;
            }
            // 交换左右两个值
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 将基准元素放到正确的位置
        arr[start] = arr[right];
        arr[right] = pivot;
        return right;
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; // 待排序数组
        quickSort(arr, 0, arr.length - 1); // 快速排序
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

The above is the basic implementation of the quick sort algorithm, using recursion to divide the array and sort. Next we analyze its performance.

The time complexity of quick sort is O(nlogn), where n is the size of the array to be sorted. The performance of quick sort mainly depends on the selection of reference elements and the rationality of division.

For the selection of reference elements, you can generally select the first element, last element, middle element, etc. of the array. Choosing appropriate reference elements can reduce the number of divisions and improve the performance of quick sort.

The rationality of division is also the key to quick sort performance. Each time the division is performed, values ​​greater than the reference element need to be placed on the right, and values ​​smaller than the reference element are placed on the left. This ensures that the left side of the reference element's position has values ​​smaller than it, and the right side has values ​​greater than it. If the division is uneven, resulting in a large difference in length between the left and right subarrays of the division result, the efficiency of quick sort may be reduced.

Quick sort is an unstable sorting algorithm because the relative order of equal elements may change during the exchange of elements.

In summary, quick sort is an efficient sorting algorithm. By reasonably selecting reference elements and dividing the array, better performance can be achieved. However, when processing large-scale data, attention needs to be paid to the selection of benchmark elements and the rationality of division to improve the efficiency of the algorithm.

The above is the detailed content of Quick sort algorithm implemented in Java and its efficiency evaluation. For more information, please follow other related articles on the PHP Chinese website!