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

在计算机科学中，排序算法和查找算法是两类最基本、最常用的算法。

• 排序算法用于将一组数据按照某种顺序（如升序、降序）进行排列；
• 查找算法用于在数据集合中寻找满足特定条件的元素。

一、排序算法

常用的排序算法：冒泡排序、选择排序、快速排序

冒泡排序（Bubble Sort）

1. 算法描述

冒泡排序是一种简单直观的排序算法。它重复地遍历待排序的序列，每次比较相邻的两个元素，如果它们的顺序错误就交换它们。这个过程会将较大的元素逐渐“冒泡”到序列的末尾。

demo code

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    // 外层循环控制遍历次数
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        // 内层循环进行相邻元素比较
        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;
            }
        }
        // 如果没有发生交换，说明序列已排序，提前结束
        if (!swapped) break;
    }
}

时间和空间复杂度

• 时间复杂度：
  • 最优情况：O(n)（当序列已经有序时）
  • 最坏情况：O(n²)
  • 平均情况：O(n²)
• 空间复杂度：O(1)（原地排序，只需常数级额外空间）
• 稳定性：稳定（相等元素的相对顺序不变）

二、选择排序（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. 时间和空间复杂度

• 时间复杂度：
  • 最优、最坏、平均情况：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定（交换可能改变相等元素的相对顺序）

三、快速排序（Quick Sort）

1. 算法描述

快速排序是对冒泡排序的一种改进，是一种高效的排序算法。它采用了分治的思想，通过选取一个基准元素（pivot），将序列划分为两部分：左侧部分小于基准，右侧部分大于基准。然后递归地对左右两部分进行排序。

2. 快速排序对冒泡排序的优化

• 减少比较次数：冒泡排序每次只交换相邻的两个元素，而快速排序通过分区，使得每次可以确定一个元素的最终位置，减少了不必要的比较和交换。
• 采用分治策略：快速排序将问题分解成较小的子问题，递归地解决，提高了效率。
• 平均时间复杂度更低：快速排序的平均时间复杂度为 O(n log n)，比冒泡排序的 O(n²) 更优。

3. demo code

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);
    }
}

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;
        }
    }
    // 将基准元素放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

注意：调用 quickSort 方法时，初始参数应为 quickSort(arr, 0, arr.length - 1);

4. 时间和空间复杂度

• 时间复杂度：
  • 最优情况：O(n log n)（每次均匀划分）
  • 最坏情况：O(n²)（每次划分不均匀，如已排序的序列）
  • 平均情况：O(n log n)
• 空间复杂度：
  • 平均情况：O(log n)（递归调用栈的深度）
  • 最坏情况：O(n)
• 稳定性：不稳定（交换可能改变相等元素的相对顺序）

四、三种排序算法的对比

• 效率比较：

  • 冒泡排序和选择排序的时间复杂度为 O(n²)，适合小规模数据排序。
  • 快速排序的平均时间复杂度为 O(n log n)，比前两者更高效，适合大规模数据排序。

• 空间复杂度：

  • 冒泡排序和选择排序的空间复杂度为 O(1)，是原地排序算法。
  • 快速排序的空间复杂度取决于递归调用栈的深度，平均为 O(log n)。

• 稳定性：

  • 冒泡排序是稳定的，选择排序和快速排序是不稳定的。

冒泡排序与快速排序的关系

• 思想上的关联：冒泡排序和快速排序都通过比较和交换元素来实现排序，但冒泡排序每次只交换相邻的两个元素，而快速排序通过分区的方式一次定位一个元素的最终位置。
• 优化方向：快速排序通过引入分治策略，减少了不必要的比较和交换，克服了冒泡排序效率低下的缺点。

2. 选择合适的排序算法

• 小规模数据或数据基本有序：可以选择冒泡排序或插入排序。
• 需要稳定排序：选择冒泡排序。
• 大规模数据：选择快速排序或其他时间复杂度为 O(n log n) 的算法（如归并排序、堆排序）。
• 空间受限：选择空间复杂度为 O(1) 的原地排序算法，如快速排序（需要注意最坏情况下的空间复杂度）。

查找算法

1. 线性查找（Linear Search）

算法描述

线性查找从数组的第一个元素开始，依次比较每个元素，直到找到目标值或遍历完整个数组。

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）

算法描述

二分查找要求数组是有序的。它通过比较目标值与中间元素的大小，决定在左半部分还是右半部分继续查找，递归或迭代地缩小查找范围。

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)（递归调用栈的深度）

3. 深度优先搜索（Depth-First Search, DFS）

算法描述

DFS 常用于图或树的遍历，从起始节点开始，尽可能深入地访问邻接节点，直到所有可达节点都被访问。

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：节点数
  • E：边数
• 空间复杂度：O(V)（递归调用栈和访问标记数组）

4. 广度优先搜索（Breadth-First Search, BFS）

算法描述

BFS 从起始节点开始，按层次逐步访问邻接节点，使用队列维护待访问的节点列表。

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)（队列和访问标记数组）

5. 插值查找（Interpolation Search）

算法描述

插值查找是改进的二分查找，假设数据是均匀分布的，通过估计目标值的位置，可能比二分查找更快。

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)（当数据均匀分布时）
• 空间复杂度：O(1)

排序算法对比

查找算法对比

结语

掌握常用的排序算法和查找算法，对于解决实际问题和优化程序性能至关重要。在选择算法时，应根据具体的应用场景、数据规模和对性能的要求，综合考虑算法的时间和空间复杂度。

• 小规模数据或基本有序的数据：可以选择简单的排序算法，如插入排序。
• 需要稳定排序：选择归并排序或冒泡排序。
• 大规模数据：选择时间复杂度为 O(n log n) 的排序算法，如快速排序、归并排序或堆排序。
• 数据有序且需要高效查找：使用二分查找。
• 数据分布均匀：插值查找可能比二分查找更高效。

在实际开发中，还可以利用编程语言提供的库函数，如 Arrays.sort()、Collections.sort()，这些方法经过高度优化，能够满足大多数排序需求。