快速排序 Java 三種實(shí)現(xiàn)

快速排序（Quick Sort）是一種高效的排序算法，它基于分治策略，將一個(gè)大問(wèn)題分解成多個(gè)小問(wèn)題，然后遞歸解決這些小問(wèn)題。本文將介紹快速排序算法的原理，并提供三種不同的 Java 實(shí)現(xiàn)方式，以幫助你更好地理解這個(gè)算法。

快速排序原理

快速排序的核心思想是選取一個(gè)基準(zhǔn)元素，然后將數(shù)組中小于基準(zhǔn)的元素移到基準(zhǔn)的左邊，大于基準(zhǔn)的元素移到基準(zhǔn)的右邊。接著，對(duì)左右兩個(gè)子數(shù)組分別遞歸地應(yīng)用相同的算法，直到整個(gè)數(shù)組有序。

下面是快速排序的基本步驟：

1. 選擇一個(gè)基準(zhǔn)元素（通常選擇第一個(gè)或最后一個(gè)元素）。
2. 將數(shù)組分成兩個(gè)子數(shù)組：小于基準(zhǔn)的元素和大于基準(zhǔn)的元素。
3. 遞歸地對(duì)子數(shù)組進(jìn)行排序。
4. 合并子數(shù)組和基準(zhǔn)元素，得到最終排序后的數(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));
    }
}

第二種實(shí)現(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) {
        // 與第一種實(shí)現(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));
    }
}

第三種實(shí)現(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) {
        // 與第一種實(shí)現(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));
    }
}

總結(jié)

快速排序是一種高效的排序算法，它的性能在平均情況下非常好。本文提供了三種不同的 Java 實(shí)現(xiàn)方式，包括遞歸、使用棧和使用Lambda表達(dá)式。你可以根據(jù)自己的需求選擇合適的實(shí)現(xiàn)方式。

如果你想了解更多有關(guān)Java編程的知識(shí)，請(qǐng)?jiān)L問(wèn)編程獅官網(wǎng)。祝你編程愉快！