Optimizing array sorting efficiency: using the quick sort algorithm in Java

How to use Java quick sort function to improve array sorting efficiency

Introduction:
In actual development, array sorting is a very common operation. For smaller size arrays, we can use simple sorting algorithms like bubble sort or insertion sort. However, when the array size is large, the efficiency of these sorting algorithms decreases significantly. At this point, we can use a more efficient sorting algorithm, such as quick sort. This article will introduce how to use Java's quick sort function to improve array sorting efficiency and provide specific code examples.

What is quick sort?
Quick sort is a sorting algorithm based on the divide and conquer idea. It divides the array into two sub-arrays by selecting a reference element, so that all elements of the left sub-array are less than or equal to the reference element, and all elements of the right sub-array are greater than or equal to the reference element. Then the left and right subarrays are quickly sorted recursively until the length of the subarray is 1 or 0.

Specific steps:

1. Select a base element.
2. Divide the array into two sub-arrays, so that all elements of the left sub-array are less than or equal to the base element, and all elements of the right sub-array are greater than or equal to the base element.
3. Quickly sort the left and right subarrays recursively.
4. Merge left subarray, base element and right subarray.

Java quick sort sample code:
The following is a sample code for using Java to implement quick sort:

// 快速排序函数
public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high); // 获取基准元素的位置
        quickSort(arr, low, pivotIndex - 1); // 对左子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high); // 对右子数组进行快速排序
    }
}

// 划分函数，返回基准元素的位置
public int partition(int[] arr, int low, int high) {
    int pivot = arr[low]; // 选择第一个元素作为基准元素
    while (low < high) {
        // 从右向左找到第一个小于基准元素的位置
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high]; // 将该元素移到左边

        // 从左向右找到第一个大于基准元素的位置
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low]; // 将该元素移到右边
    }
    arr[low] = pivot; // 将基准元素放到最终位置
    return low; // 返回基准元素的位置
}

Usage example:
The following is a quick sort function using Sample code for sorting the array:

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 7, 1, 3, 9, 2};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

The running result is: [1, 2, 3, 5, 7, 9], the array has been sorted from small to large.

Summary:
When dealing with large-scale array sorting, using the quick sort algorithm can significantly improve efficiency. Quick sort uses the divide-and-conquer idea to divide the array into two sub-arrays by selecting the reference element, and recursively sort the sub-arrays, and finally merge them to obtain an ordered array. This article provides specific code examples for implementing quick sort using Java, hoping to help readers better understand and apply the quick sort algorithm.

The above is the detailed content of Optimizing array sorting efficiency: using the quick sort algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!