快速排序(Quick Sort)是一種高效的排序算法,它基于分治策略,將一個大問題分解成多個小問題,然后遞歸解決這些小問題。本文將介紹快速排序算法的原理,并提供三種不同的 Java 實現(xiàn)方式,以幫助你更好地理解這個算法。
快速排序原理
快速排序的核心思想是選取一個基準元素,然后將數(shù)組中小于基準的元素移到基準的左邊,大于基準的元素移到基準的右邊。接著,對左右兩個子數(shù)組分別遞歸地應用相同的算法,直到整個數(shù)組有序。
下面是快速排序的基本步驟:
- 選擇一個基準元素(通常選擇第一個或最后一個元素)。
- 將數(shù)組分成兩個子數(shù)組:小于基準的元素和大于基準的元素。
- 遞歸地對子數(shù)組進行排序。
- 合并子數(shù)組和基準元素,得到最終排序后的數(shù)組。
第一種實現(xiàn):使用遞歸
public class QuickSort { 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) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
} else {
break;
}
}
int temp = arr[low];
arr[low] = arr[right];
arr[right] = temp;
return right;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 4, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
第二種實現(xiàn):使用Stack
import java.util.Arrays;
import java.util.Stack;
public class QuickSortUsingStack {
public static void quickSort(int[] arr, int low, int high) {
Stack<Integer> stack = new Stack<>();
stack.push(low);
stack.push(high);
while (!stack.isEmpty()) {
high = stack.pop();
low = stack.pop();
int pivotIndex = partition(arr, low, high);
if (pivotIndex - 1 > low) {
stack.push(low);
stack.push(pivotIndex - 1);
}
if (pivotIndex + 1 < high) {
stack.push(pivotIndex + 1);
stack.push(high);
}
}
}
public static int partition(int[] arr, int low, int high) {
// 與第一種實現(xiàn)相同
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 4, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
第三種實現(xiàn):使用Lambdas
import java.util.Arrays;
import java.util.function.Predicate;
public class QuickSortUsingLambdas {
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) {
// 與第一種實現(xiàn)相同
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 4, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
總結
快速排序是一種高效的排序算法,它的性能在平均情況下非常好。本文提供了三種不同的 Java 實現(xiàn)方式,包括遞歸、使用棧和使用Lambda表達式。你可以根據(jù)自己的需求選擇合適的實現(xiàn)方式。
如果你想了解更多有關Java編程的知識,請訪問編程獅官網(wǎng)。祝你編程愉快!