Quick sort algorithm implemented in Java language

An implementation method of quick sorting algorithm based on Java language

Quick sorting is an efficient sorting algorithm, which is often used to sort large amounts of data. This article will introduce an implementation method of quick sorting algorithm based on Java language and provide specific code examples.

The basic idea of ​​quick sort is to divide the data to be sorted into two independent parts. For example, using one element as the standard value, elements smaller than the value are placed on the left, and elements larger than the value are placed on the left. right. Then quickly sort these two parts separately until the entire sequence is sorted.

First, we need to implement a Partition function to divide the data. This function divides the entire sequence into two parts by selecting a Pivot (generally selecting the first element in the sequence) and returns the position of the Pivot. The specific code is as follows:

public class QuickSort {
    public int partition(int[] array, int low, int high) {
        int pivot = array[low]; // 选择第一个元素作为Pivot
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            array[low] = array[high]; // 将小于Pivot的元素移到左边

            while (low < high && array[low] <= pivot) {
                low++;
            }
            array[high] = array[low]; // 将大于Pivot的元素移到右边
        }
        array[low] = pivot; // 将Pivot放到正确的位置
        return low; // 返回Pivot的位置
    }
}

Next, we need to implement the QuickSort function to sort the entire sequence. The specific code is as follows:

public class QuickSort {
    // ... 上面的代码省略 ...

    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high); // 划分序列
            quickSort(array, low, pivotIndex - 1); // 对左边序列进行快速排序
            quickSort(array, pivotIndex + 1, high); // 对右边序列进行快速排序
        }
    }
}

Finally, we can use the QuickSort class to sort an integer array. The specific code is as follows:

public class Main {
    public static void main(String[] args) {
        int[] array = {5, 2, 6, 3, 1, 4}; // 待排序的数组

        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(array, 0, array.length - 1); // 对数组进行快速排序

        System.out.print("排序结果：");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

The above is a method to implement the quick sort algorithm based on Java language. By implementing the Partition function and QuickSort function, we can quickly sort an integer array. This algorithm has a time complexity of O(nlogn) and is a very efficient sorting algorithm.

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