Java怎么實現冒泡排序，選擇排序，快速排序

Java怎么實現冒泡排序，選擇排序，快速排序

在Java編程中，排序算法是非?；A且重要的內容。本文將介紹如何使用Java實現三種常見的排序算法：冒泡排序、選擇排序和快速排序。每種排序算法都有其獨特的實現方式和適用場景，理解它們的原理和實現方法對于提升編程能力非常有幫助。

1. 冒泡排序

冒泡排序是一種簡單的排序算法，它重復地遍歷要排序的列表，比較相鄰的元素并交換它們的位置，直到整個列表排序完成。冒泡排序的時間復雜度為O(n^2)，適用于小規模數據的排序。

實現代碼

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交換arr[j]和arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("排序后的數組:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

代碼解析

• bubbleSort方法接收一個整數數組作為參數。
• 外層循環控制遍歷的次數，內層循環用于比較相鄰元素并交換位置。
• 每次外層循環結束后，最大的元素會被移動到數組的末尾。
• 最終，數組會按升序排列。

2. 選擇排序

選擇排序是一種簡單直觀的排序算法。它的工作原理是每次從未排序的部分中選擇最?。ɑ蜃畲螅┑脑?，放到已排序部分的末尾。選擇排序的時間復雜度也是O(n^2)，適用于小規模數據的排序。

實現代碼

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交換arr[i]和arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的數組:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

代碼解析

• selectionSort方法接收一個整數數組作為參數。
• 外層循環控制每次選擇最小元素的起始位置。
• 內層循環用于查找未排序部分中的最小元素。
• 每次外層循環結束后，最小元素會被放到已排序部分的末尾。
• 最終，數組會按升序排列。

3. 快速排序

快速排序是一種高效的排序算法，采用分治法策略。它通過選擇一個“基準”元素，將數組分為兩部分，一部分小于基準，另一部分大于基準，然后遞歸地對這兩部分進行排序?？焖倥判虻钠骄鶗r間復雜度為O(n log n)，適用于大規模數據的排序。

實現代碼

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 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++;
                // 交換arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 交換arr[i+1]和arr[high]（即基準元素）
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        quickSort(arr, 0, n - 1);
        System.out.println("排序后的數組:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

代碼解析

• quickSort方法接收一個整數數組以及數組的起始和結束索引作為參數。
• partition方法用于將數組分為兩部分，并返回基準元素的最終位置。
• 在partition方法中，選擇數組的最后一個元素作為基準元素。
• 通過遍歷數組，將小于基準元素的元素移動到基準元素的左側，大于基準元素的元素移動到右側。
• 遞歸地對基準元素左右兩側的子數組進行排序。
• 最終，數組會按升序排列。

總結

本文介紹了三種常見的排序算法：冒泡排序、選擇排序和快速排序，并提供了Java實現代碼。冒泡排序和選擇排序雖然簡單，但時間復雜度較高，適用于小規模數據的排序?？焖倥判騽t是一種高效的排序算法，適用于大規模數據的排序。理解這些排序算法的原理和實現方法，有助于在實際編程中選擇合適的排序策略。