Detailed explanation of the principle and implementation of Java quick sort
Quick Sort is a commonly used sorting algorithm. Its implementation is simple and efficient. It is one of the classic recursive algorithms. one. This article will introduce the principle and implementation of quick sort in detail, and provide specific Java code examples.
The general steps of quick sorting are as follows:
(1) Select a benchmark element and divide the sequence into two parts, so that the elements on the left are less than or equal to the benchmark, and the elements on the right are greater than or equal to the benchmark;
(2) Quickly sort the left and right parts recursively.
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); } } private 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; } private 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 = {9, 2, 4, 7, 1, 5, 3, 8, 6}; System.out.println("Before sorting:"); for (int num : arr) { System.out.print(num + " "); } quickSort(arr, 0, arr.length - 1); System.out.println(" After sorting:"); for (int num : arr) { System.out.print(num + " "); } } }
In the above code, we define a static method quickSort
, which accepts an integer array, starting and ending index as parameters. In the quickSort
method, first determine whether the starting index is smaller than the ending index. If the condition is met, select the base element and perform the partition operation through the partition
method. partition
In the method, we use the last element as the base element, traverse the elements between the starting index and the end index, and exchange elements smaller than the base element with elements larger than the base element. Finally, swap the base element to its final position and return that position.
In the main
method, we create an integer array and initialize it. Then, call the quickSort
method to sort the array and output the results before and after sorting.
Since quick sort is implemented recursively, stack overflow may occur in the worst case. In order to solve this problem, you can use a non-recursive method or optimize the recursive call.
Quick sort is a non-stable sorting algorithm, that is, the relative order of the same elements may be changed.
Summary:
Quick sort is a classic sorting algorithm with a simple and efficient principle. This article helps readers understand and master the ideas and implementation methods of the quick sort algorithm by analyzing the principle of quick sort in detail and providing specific Java implementation code. Through practice and optimization, we can better apply the quick sort algorithm to solve practical problems.
The above is the detailed content of In-depth discussion of the principles and implementation steps of Java quick sort algorithm. For more information, please follow other related articles on the PHP Chinese website!