How to implement quick sort algorithm using java

How to use Java to implement the quick sort algorithm

Quick Sort (Quick Sort) is a commonly used and efficient sorting algorithm. Its basic idea is to adopt the divide and conquer strategy (Divide and Conquer). By selecting one element at a time as the benchmark value, the array to be sorted is divided into two parts, one part is smaller than the benchmark value, and the other part is larger than the benchmark value, and then the two parts are divided into two parts. Perform partial recursive sorting, and finally achieve sorting of the entire array.

Below we will introduce in detail how to use Java language to implement the quick sort algorithm and provide specific code examples.

1. Algorithm implementation steps:

   • Select a benchmark value (can be any number, generally select the first element of the array);
   • Divide the array into two parts. The elements in the left part are all smaller than the benchmark value, and the elements in the right part are larger than the benchmark value;
   • Quickly sort the left and right parts recursively.
2. Java code example:

public class QuickSort {
    
    public static void main(String[] args) {
        int[] arr = {5, 7, 2, 9, 3, 6, 1, 8, 4};
        quickSort(arr, 0, arr.length - 1);
        printArray(arr);
    }
    
    public static 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 static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];  // 选择数组的第一个元素作为基准值
        int left = low + 1;
        int right = high;
        
        while (true) {
            while (left <= right && arr[left] < pivot) {  // 从左往右找到第一个大于或等于基准值的元素
                left++;
            }
            while (left <= right && arr[right] > pivot) {  // 从右往左找到第一个小于或等于基准值的元素
                right--;
            }
            if (left > right) {
                break;  // 左右指针相遇时退出循环
            }
            swap(arr, left, right);  // 交换左右指针指向的元素
        }
        swap(arr, low, right);  // 将基准值放回正确的位置
        return 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 printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

3. Performance analysis:

   • Time complexity: quick sort The average time complexity is O(nlogn), in the worst case it is O(n^2), in the best case it is O(n);
   • Space complexity: The space complexity of quick sorting is O(logn), due to stack space for recursive calls.

Through the above introduction, we have learned how to use Java language to implement the quick sort algorithm, and understood its basic ideas, steps and performance analysis. Quick sort is a commonly used sorting algorithm that can efficiently sort any type of data, and is especially suitable for large-scale data sorting.

The above is the detailed content of How to implement quick sort algorithm using java. For more information, please follow other related articles on the PHP Chinese website!