常用的排序算法和查找算法

在計算機科學中奏司，排序算法和查找算法是兩類最基本、最常用的算法唤反。

• 排序算法用于將一組數(shù)據(jù)按照某種順序（如升序谍失、降序）進行排列眶俩；
• 查找算法用于在數(shù)據(jù)集合中尋找滿足特定條件的元素。

一快鱼、排序算法

常用的排序算法：冒泡排序、選擇排序纲岭、快速排序

冒泡排序（Bubble Sort）

1. 算法描述

冒泡排序是一種簡單直觀的排序算法抹竹。它重復地遍歷待排序的序列，每次比較相鄰的兩個元素止潮，如果它們的順序錯誤就交換它們窃判。這個過程會將較大的元素逐漸“冒泡”到序列的末尾。

demo code

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    // 外層循環(huán)控制遍歷次數(shù)
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        // 內(nèi)層循環(huán)進行相鄰元素比較
        for (int j = 0; j < n - 1 - i; 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;
                swapped = true;
            }
        }
        // 如果沒有發(fā)生交換喇闸，說明序列已排序袄琳，提前結(jié)束
        if (!swapped) break;
    }
}

時間和空間復雜度

• 時間復雜度：
  • 最優(yōu)情況：O(n)（當序列已經(jīng)有序時）
  • 最壞情況：O(n2)
  • 平均情況：O(n2)
• 空間復雜度：O(1)（原地排序询件，只需常數(shù)級額外空間）
• 穩(wěn)定性：穩(wěn)定（相等元素的相對順序不變）

二、選擇排序（Selection Sort）

1. 算法描述

選擇排序是一種簡單的排序算法唆樊。它的基本思想是：每一輪從未排序的部分中選出最型鹄拧（或最大）的元素，放到已排序部分的末尾逗旁，直到所有元素都被排序嘿辟。

2. demo code

public static void selectionSort(int[] arr) {
    int n = arr.length;
    // 一共進行 n - 1 輪選擇
    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;
            }
        }
        // 將最小值交換到已排序部分的末尾
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

3. 時間和空間復雜度

• 時間復雜度：
  • 最優(yōu)、最壞片效、平均情況：O(n2)
• 空間復雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定（交換可能改變相等元素的相對順序）

三红伦、快速排序（Quick Sort）

1. 算法描述

快速排序是對冒泡排序的一種改進，是一種高效的排序算法淀衣。它采用了分治的思想昙读，通過選取一個基準元素（pivot），將序列劃分為兩部分：左側(cè)部分小于基準膨桥，右側(cè)部分大于基準蛮浑。然后遞歸地對左右兩部分進行排序。

2. 快速排序?qū)γ芭菖判虻膬?yōu)化

• 減少比較次數(shù)：冒泡排序每次只交換相鄰的兩個元素国撵，而快速排序通過分區(qū)陵吸，使得每次可以確定一個元素的最終位置，減少了不必要的比較和交換介牙。
• 采用分治策略：快速排序?qū)栴}分解成較小的子問題壮虫，遞歸地解決，提高了效率环础。
• 平均時間復雜度更低：快速排序的平均時間復雜度為 O(n log n)囚似，比冒泡排序的 O(n2) 更優(yōu)蜒蕾。

3. demo code

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 對數(shù)組進行分區(qū)粟按，返回基準元素的正確位置
        int pivotIndex = partition(arr, low, high);
        // 遞歸排序基準元素左側(cè)的子數(shù)組
        quickSort(arr, low, pivotIndex - 1);
        // 遞歸排序基準元素右側(cè)的子數(shù)組
        quickSort(arr, pivotIndex + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    // 選擇最右邊的元素作為基準
    int pivot = arr[high];
    int i = low - 1;
    // 遍歷數(shù)組于毙，將小于基準的元素移動到左側(cè)
    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;
        }
    }
    // 將基準元素放到正確的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

注意：調(diào)用 quickSort 方法時纷跛，初始參數(shù)應為 quickSort(arr, 0, arr.length - 1);

4. 時間和空間復雜度

• 時間復雜度：
  • 最優(yōu)情況：O(n log n)（每次均勻劃分）
  • 最壞情況：O(n2)（每次劃分不均勻偶宫，如已排序的序列）
  • 平均情況：O(n log n)
• 空間復雜度：
  • 平均情況：O(log n)（遞歸調(diào)用棧的深度）
  • 最壞情況：O(n)
• 穩(wěn)定性：不穩(wěn)定（交換可能改變相等元素的相對順序）

四宣虾、三種排序算法的對比

• 效率比較：

  • 冒泡排序和選擇排序的時間復雜度為 O(n2)蓝厌，適合小規(guī)模數(shù)據(jù)排序诞帐。
  • 快速排序的平均時間復雜度為 O(n log n)角雷，比前兩者更高效祸穷，適合大規(guī)模數(shù)據(jù)排序。

• 空間復雜度：

  • 冒泡排序和選擇排序的空間復雜度為 O(1)勺三，是原地排序算法雷滚。
  • 快速排序的空間復雜度取決于遞歸調(diào)用棧的深度，平均為 O(log n)吗坚。

• 穩(wěn)定性：

  • 冒泡排序是穩(wěn)定的祈远，選擇排序和快速排序是不穩(wěn)定的呆万。

冒泡排序與快速排序的關(guān)系

• 思想上的關(guān)聯(lián)：冒泡排序和快速排序都通過比較和交換元素來實現(xiàn)排序，但冒泡排序每次只交換相鄰的兩個元素车份，而快速排序通過分區(qū)的方式一次定位一個元素的最終位置谋减。
• 優(yōu)化方向：快速排序通過引入分治策略，減少了不必要的比較和交換躬充，克服了冒泡排序效率低下的缺點逃顶。

2. 選擇合適的排序算法

• 小規(guī)模數(shù)據(jù)或數(shù)據(jù)基本有序：可以選擇冒泡排序或插入排序。
• 需要穩(wěn)定排序：選擇冒泡排序充甚。
• 大規(guī)模數(shù)據(jù)：選擇快速排序或其他時間復雜度為 O(n log n) 的算法（如歸并排序以政、堆排序）。
• 空間受限：選擇空間復雜度為 O(1) 的原地排序算法伴找，如快速排序（需要注意最壞情況下的空間復雜度）盈蛮。

查找算法

1. 線性查找（Linear Search）

算法描述

線性查找從數(shù)組的第一個元素開始，依次比較每個元素技矮，直到找到目標值或遍歷完整個數(shù)組抖誉。

Demo code

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1; // 未找到
}

時間和空間復雜度

• 時間復雜度：
  • 最佳情況：O(1)（目標值在第一個位置）
  • 最差情況：O(n)
  • 平均情況：O(n)
• 空間復雜度：O(1)

2. 二分查找（Binary Search）

算法描述

二分查找要求數(shù)組是有序的。它通過比較目標值與中間元素的大小衰倦，決定在左半部分還是右半部分繼續(xù)查找袒炉，遞歸或迭代地縮小查找范圍。

demo code

public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 防止溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // 未找到
}

時間和空間復雜度

• 時間復雜度：
  • 最佳情況：O(1)（目標值在中間位置）
  • 最差情況：O(log n)
  • 平均情況：O(log n)
• 空間復雜度：
  • 迭代版本：O(1)
  • 遞歸版本：O(log n)（遞歸調(diào)用棧的深度）

3. 深度優(yōu)先搜索（Depth-First Search, DFS）

算法描述

DFS 常用于圖或樹的遍歷樊零，從起始節(jié)點開始我磁，盡可能深入地訪問鄰接節(jié)點，直到所有可達節(jié)點都被訪問驻襟。

demo code

// 假設使用鄰接表表示圖
public static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    System.out.print(node + " ");
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

時間和空間復雜度

• 時間復雜度：O(V + E)
  • V：節(jié)點數(shù)
  • E：邊數(shù)
• 空間復雜度：O(V)（遞歸調(diào)用棧和訪問標記數(shù)組）

4. 廣度優(yōu)先搜索（Breadth-First Search, BFS）

算法描述

BFS 從起始節(jié)點開始夺艰，按層次逐步訪問鄰接節(jié)點，使用隊列維護待訪問的節(jié)點列表沉衣。

demo code

public static void bfs(int startNode, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    visited[startNode] = true;
    queue.offer(startNode);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

時間和空間復雜度

• 時間復雜度：O(V + E)
• 空間復雜度：O(V)（隊列和訪問標記數(shù)組）

5. 插值查找（Interpolation Search）

算法描述

插值查找是改進的二分查找郁副，假設數(shù)據(jù)是均勻分布的，通過估計目標值的位置豌习，可能比二分查找更快存谎。

demo code

public static int interpolationSearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low == high) {
            if (arr[low] == target) return low;
            else return -1;
        }
        int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        if (arr[pos] == target) return pos;
        else if (arr[pos] < target) low = pos + 1;
        else high = pos - 1;
    }
    return -1;
}

時間和空間復雜度

• 時間復雜度：
  • 最佳情況：O(1)
  • 最差情況：O(n)
  • 平均情況：O(log log n)（當數(shù)據(jù)均勻分布時）
• 空間復雜度：O(1)

排序算法對比

查找算法對比

結(jié)語

掌握常用的排序算法和查找算法，對于解決實際問題和優(yōu)化程序性能至關(guān)重要肥隆。在選擇算法時愕贡，應根據(jù)具體的應用場景、數(shù)據(jù)規(guī)模和對性能的要求巷屿，綜合考慮算法的時間和空間復雜度。

• 小規(guī)模數(shù)據(jù)或基本有序的數(shù)據(jù)：可以選擇簡單的排序算法墩虹，如插入排序嘱巾。
• 需要穩(wěn)定排序：選擇歸并排序或冒泡排序憨琳。
• 大規(guī)模數(shù)據(jù)：選擇時間復雜度為 O(n log n) 的排序算法，如快速排序旬昭、歸并排序或堆排序篙螟。
• 數(shù)據(jù)有序且需要高效查找：使用二分查找。
• 數(shù)據(jù)分布均勻：插值查找可能比二分查找更高效问拘。

在實際開發(fā)中遍略，還可以利用編程語言提供的庫函數(shù)，如 Arrays.sort()骤坐、Collections.sort()绪杏，這些方法經(jīng)過高度優(yōu)化，能夠滿足大多數(shù)排序需求纽绍。