LeetCode排序与搜索算法全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 14:07:34

4390

文章被收录于专栏：AI SPPECHAI SPPECH

一、排序算法基础

1.1 排序算法的基本概念

排序算法是一种将一组数据按照特定的顺序（如升序或降序）排列的算法。排序算法的性能通常用时间复杂度、空间复杂度和稳定性来衡量：

时间复杂度：指算法执行所需的时间，通常用大O符号表示
空间复杂度：指算法执行所需的额外空间
稳定性：指排序后，相同值的元素的相对顺序是否保持不变

排序算法可以分为内部排序和外部排序：

内部排序：所有数据都在内存中进行排序
外部排序：数据量太大，无法全部放入内存，需要借助外部存储设备进行排序

1.2 排序算法的分类

常用的内部排序算法可以分为以下几类：

比较排序：通过比较元素的大小来决定它们的相对顺序
- 交换排序：冒泡排序、快速排序
- 插入排序：直接插入排序、希尔排序
- 选择排序：直接选择排序、堆排序
- 归并排序：二路归并排序、多路归并排序
非比较排序：不通过比较元素的大小来决定它们的相对顺序
- 计数排序
- 桶排序
- 基数排序

1.3 常见排序算法的性能比较

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
希尔排序	O(n^1.3)	O(n²)	O(n)	O(1)	不稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(logn)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
桶排序	O(n+k)	O(n²)	O(n)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

二、基础排序算法

2.1 冒泡排序（Bubble Sort）

冒泡排序是一种简单的交换排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

算法步骤：

比较相邻的元素。如果第一个比第二个大，就交换它们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
针对所有的元素重复以上的步骤，除了最后一个
重复步骤1~3，直到排序完成

Java实现：

public void bubbleSort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换元素
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                swapped = true;
            }
        }
        // 如果没有交换，说明已经排序完成
        if (!swapped) {
            break;
        }
    }
}

时间复杂度：O(n²)，其中n是数组的长度 空间复杂度：O(1) 稳定性：稳定

2.2 选择排序（Selection Sort）

选择排序是一种简单的选择排序算法，它的基本思想是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（或最大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

算法步骤：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
重复第二步，直到所有元素均排序完毕

Java实现：

public void selectionSort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        // 寻找未排序部分的最小元素
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小元素与未排序部分的第一个元素交换
        if (minIndex != i) {
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }
}

时间复杂度：O(n²)，其中n是数组的长度 空间复杂度：O(1) 稳定性：不稳定

2.3 插入排序（Insertion Sort）

插入排序是一种简单的插入排序算法，它的基本思想是：将待排序序列分为已排序部分和未排序部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置，直到所有元素都插入完毕。

算法步骤：

将第一个元素视为已排序部分
取出下一个元素，在已排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

Java实现：

public void insertionSort(int[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        int key = nums[i];
        int j = i - 1;
        // 将大于key的元素向后移动
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}

时间复杂度：O(n²)，其中n是数组的长度 空间复杂度：O(1) 稳定性：稳定

三、高级排序算法

3.1 快速排序（Quick Sort）

快速排序是一种高效的交换排序算法，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法步骤：

选择一个元素作为基准（通常选择第一个元素、最后一个元素或中间元素）
将小于基准的元素放在基准的左边，大于基准的元素放在基准的右边
对基准左边和右边的子序列分别进行快速排序

Java实现：

public void quickSort(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
}

private void quickSort(int[] nums, int low, int high) {
    if (low < high) {
        // 获取分区点
        int pivotIndex = partition(nums, low, high);
        // 递归排序左子数组
        quickSort(nums, low, pivotIndex - 1);
        // 递归排序右子数组
        quickSort(nums, pivotIndex + 1, high);
    }
}

private int partition(int[] nums, int low, int high) {
    // 选择最右边的元素作为基准
    int pivot = nums[high];
    // i表示小于基准的元素的最右边位置
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            i++;
            // 交换元素
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    // 将基准放到正确的位置
    int temp = nums[i + 1];
    nums[i + 1] = nums[high];
    nums[high] = temp;
    return i + 1;
}

时间复杂度：

平均情况：O(nlogn)，其中n是数组的长度
最坏情况：O(n²)，当数组已经排序或接近排序时
最好情况：O(nlogn)，每次分区都将数组分成大小相等的两部分

空间复杂度：O(logn)，递归调用栈的深度 稳定性：不稳定

3.2 归并排序（Merge Sort）

归并排序是一种高效的归并排序算法，它的基本思想是：将待排序序列分成若干个子序列，每个子序列都是有序的，然后将有序子序列合并成整体有序序列。

算法步骤：

将序列分成两个长度大致相等的子序列
对这两个子序列分别进行归并排序
将排好序的子序列合并成一个有序序列

Java实现：

public void mergeSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return;
    }
    int[] temp = new int[nums.length];
    mergeSort(nums, 0, nums.length - 1, temp);
}

private void mergeSort(int[] nums, int left, int right, int[] temp) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左子数组
        mergeSort(nums, left, mid, temp);
        // 递归排序右子数组
        mergeSort(nums, mid + 1, right, temp);
        // 合并两个有序子数组
        merge(nums, left, mid, right, temp);
    }
}

private void merge(int[] nums, int left, int mid, int right, int[] temp) {
    int i = left; // 左子数组的起始索引
    int j = mid + 1; // 右子数组的起始索引
    int k = 0; // 临时数组的起始索引
    // 比较左右子数组的元素，将较小的元素放入临时数组
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    // 将左子数组中剩余的元素放入临时数组
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    // 将右子数组中剩余的元素放入临时数组
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    // 将临时数组中的元素复制回原数组
    k = 0;
    while (left <= right) {
        nums[left++] = temp[k++];
    }
}

时间复杂度：O(nlogn)，其中n是数组的长度 空间复杂度：O(n)，需要一个临时数组来存储合并结果 稳定性：稳定

3.3 堆排序（Heap Sort）

堆排序是一种高效的选择排序算法，它的基本思想是：将待排序序列构建成一个大顶堆（或小顶堆），然后将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端，然后重新调整堆，重复这个过程，直到整个序列有序。

算法步骤：

将待排序序列构建成一个大顶堆
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
重新调整堆，使其满足堆的性质
重复步骤2~3，直到整个序列有序

Java实现：

public void heapSort(int[] nums) {
    int n = nums.length;
    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    // 一个个交换元素
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素（最大值）与当前堆的最后一个元素交换
        int temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        // 重新调整堆
        heapify(nums, i, 0);
    }
}

// 调整堆的函数
private void heapify(int[] nums, int n, int i) {
    int largest = i; // 初始化largest为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    // 如果左子节点大于根节点
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    // 如果右子节点大于当前最大值
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    // 如果最大值不是根节点
    if (largest != i) {
        int swap = nums[i];
        nums[i] = nums[largest];
        nums[largest] = swap;
        // 递归地调整受影响的子树
        heapify(nums, n, largest);
    }
}

时间复杂度：O(nlogn)，其中n是数组的长度 空间复杂度：O(1) 稳定性：不稳定

四、搜索算法基础

4.1 搜索算法的基本概念

搜索算法是一种用于在数据结构中查找特定元素的算法。搜索算法的性能通常用时间复杂度和空间复杂度来衡量。

搜索算法可以分为以下几类：

顺序搜索：从数据结构的一端开始，依次检查每个元素，直到找到目标元素或遍历完整个数据结构
二分搜索：在有序的数据结构中，通过不断将搜索范围缩小一半来查找目标元素
插值搜索：在有序的数据结构中，根据目标元素的值与数据结构中元素的分布情况，估计目标元素的位置
斐波那契搜索：在有序的数据结构中，使用斐波那契数列来确定搜索点
树搜索：在树结构中查找目标元素，如二叉搜索树搜索、平衡树搜索等
哈希搜索：使用哈希表来存储和查找元素

4.2 顺序搜索（Linear Search）

顺序搜索是一种简单的搜索算法，它的基本思想是：从数据结构的一端开始，依次检查每个元素，直到找到目标元素或遍历完整个数据结构。

算法步骤：

从数组的第一个元素开始，依次与目标值进行比较
如果某个元素等于目标值，则返回该元素的索引
如果遍历完整个数组都没有找到目标值，则返回-1表示未找到

Java实现：

public int linearSearch(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

时间复杂度：O(n)，其中n是数组的长度 空间复杂度：O(1)

4.3 二分搜索（Binary Search）

二分搜索是一种高效的搜索算法，它的基本思想是：在有序的数据结构中，通过不断将搜索范围缩小一半来查找目标元素。

算法步骤：

确定搜索范围的左右边界（初始时，左边界为0，右边界为数组长度减1）
计算中间位置的索引（mid = left + (right - left) / 2）
如果中间位置的元素等于目标值，则返回该位置的索引
如果中间位置的元素大于目标值，则将右边界更新为mid - 1，在左半部分继续搜索
如果中间位置的元素小于目标值，则将左边界更新为mid + 1，在右半部分继续搜索
重复步骤2~5，直到找到目标元素或左边界大于右边界（表示未找到）

Java实现：

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

时间复杂度：O(logn)，其中n是数组的长度 空间复杂度：O(1)

五、LeetCode中的排序问题

5.1 排序数组（LeetCode 912）

题目描述：给你一个整数数组 nums，请你将该数组升序排列。

示例：输入：nums = [5,2,3,1] 输出：[1,2,3,5]

解题思路：这是一个经典的排序问题，我们可以使用各种排序算法来解决。这里我们使用快速排序来实现。

public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

private void quickSort(int[] nums, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(nums, low, high);
        quickSort(nums, low, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, high);
    }
}

private int partition(int[] nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums, i, j);
        }
    }
    swap(nums, i + 1, high);
    return i + 1;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

5.2 最大间距（LeetCode 164）

题目描述：给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。

示例：输入：nums = [3,6,9,1] 输出：3 解释：排序后的数组是 [1,3,6,9]，相邻元素 (3,6) 和 (6,9) 之间的差值都为 3，所以返回 3。

解题思路：我们可以先对数组进行排序，然后遍历排序后的数组，计算相邻元素之间的差值，并记录最大值。这里我们可以使用基数排序来优化排序的时间复杂度。

public int maximumGap(int[] nums) {
    int n = nums.length;
    if (n < 2) {
        return 0;
    }
    // 使用基数排序对数组进行排序
    radixSort(nums);
    // 计算相邻元素之间的最大差值
    int maxGap = 0;
    for (int i = 1; i < n; i++) {
        maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

private void radixSort(int[] nums) {
    // 找出数组中的最大值
    int max = Integer.MIN_VALUE;
    for (int num : nums) {
        max = Math.max(max, num);
    }
    // 计算最大值的位数
    int maxDigits = 0;
    while (max > 0) {
        maxDigits++;
        max /= 10;
    }
    // 对每一位进行计数排序
    int exp = 1; // 1, 10, 100, ...
    int[] temp = new int[nums.length];
    for (int i = 0; i < maxDigits; i++) {
        int[] count = new int[10]; // 0-9的计数器
        // 统计每个数字出现的次数
        for (int num : nums) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }
        // 计算累计次数（用于确定每个数字在临时数组中的位置）
        for (int j = 1; j < 10; j++) {
            count[j] += count[j - 1];
        }
        // 从后向前遍历原数组，保证排序的稳定性
        for (int j = nums.length - 1; j >= 0; j--) {
            int digit = (nums[j] / exp) % 10;
            temp[count[digit] - 1] = nums[j];
            count[digit]--;
        }
        // 将临时数组中的元素复制回原数组
        System.arraycopy(temp, 0, nums, 0, nums.length);
        exp *= 10;
    }
}

时间复杂度：O(n*k)，其中n是数组的长度，k是数组中最大元素的位数 空间复杂度：O(n)

5.3 合并区间（LeetCode 56）

题目描述：给出一个区间的集合，请合并所有重叠的区间。

示例：输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6].

解题思路：我们可以先按照区间的起始位置对区间进行排序，然后遍历排序后的区间，合并重叠的区间。

public int[][] merge(int[][] intervals) {
    if (intervals == null || intervals.length <= 1) {
        return intervals;
    }
    // 按照区间的起始位置排序
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> merged = new ArrayList<>();
    // 添加第一个区间到结果集
    merged.add(intervals[0]);
    // 遍历剩余的区间
    for (int i = 1; i < intervals.length; i++) {
        // 获取结果集中最后一个区间
        int[] lastInterval = merged.get(merged.size() - 1);
        // 当前区间的起始位置
        int currStart = intervals[i][0];
        // 当前区间的结束位置
        int currEnd = intervals[i][1];
        // 结果集中最后一个区间的结束位置
        int lastEnd = lastInterval[1];
        // 如果当前区间的起始位置小于等于结果集中最后一个区间的结束位置，说明它们重叠
        if (currStart <= lastEnd) {
            // 合并区间，取两个区间结束位置的最大值
            lastInterval[1] = Math.max(lastEnd, currEnd);
        } else {
            // 如果不重叠，将当前区间添加到结果集
            merged.add(intervals[i]);
        }
    }
    // 将结果集转换为数组并返回
    return merged.toArray(new int[merged.size()][]);
}

时间复杂度：O(nlogn)，其中n是区间的数量，主要是排序的时间复杂度 空间复杂度：O(n)，用于存储合并后的区间

5.4 数组中的第K个最大元素（LeetCode 215）

题目描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：输入：[3,2,1,5,6,4] 和 k = 2 输出：5

解题思路：我们可以使用快速选择算法来解决这个问题。快速选择算法是快速排序的一个变种，它的基本思想是：通过一趟分区，将数组分成两部分，然后只递归地在包含第k大元素的那一部分继续查找。

public int findKthLargest(int[] nums, int k) {
    // 转换为第n-k小的元素（0-based）
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

private int quickSelect(int[] nums, int low, int high, int k) {
    if (low == high) {
        return nums[low];
    }
    // 分区
    int pivotIndex = partition(nums, low, high);
    // 如果分区点的索引等于k，说明找到了第k小的元素
    if (pivotIndex == k) {
        return nums[pivotIndex];
    } else if (pivotIndex < k) {
        // 如果分区点的索引小于k，在右半部分继续查找
        return quickSelect(nums, pivotIndex + 1, high, k);
    } else {
        // 如果分区点的索引大于k，在左半部分继续查找
        return quickSelect(nums, low, pivotIndex - 1, k);
    }
}

private int partition(int[] nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums, i, j);
        }
    }
    swap(nums, i + 1, high);
    return i + 1;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

时间复杂度：

平均情况：O(n)，其中n是数组的长度
最坏情况：O(n²)，当数组已经排序或接近排序时

空间复杂度：O(logn)，递归调用栈的深度

六、LeetCode中的搜索问题

6.1 二分查找（LeetCode 704）

题目描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例：输入：nums = [-1,0,3,5,9,12], target = 9 输出：4 解释：9 出现在 nums 中并且下标为 4

解题思路：这是一个经典的二分搜索问题，我们可以使用标准的二分搜索算法来解决。

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

时间复杂度：O(logn)，其中n是数组的长度 空间复杂度：O(1)

6.2 搜索插入位置（LeetCode 35）

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例：输入：nums = [1,3,5,6], target = 5 输出：2

解题思路：我们可以使用二分搜索来找到目标值在数组中的位置或插入位置。如果找到目标值，返回其索引；如果没有找到，返回左指针的位置，该位置就是目标值应该插入的位置。

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

时间复杂度：O(logn)，其中n是数组的长度 空间复杂度：O(1)

6.3 在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

示例：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

解题思路：我们可以使用两次二分搜索，分别找到目标值在数组中的第一个位置和最后一个位置。

public int[] searchRange(int[] nums, int target) {
    int[] result = {-1, -1};
    if (nums == null || nums.length == 0) {
        return result;
    }
    // 找到第一个等于target的位置
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    // 如果没有找到target，返回[-1, -1]
    if (nums[left] != target) {
        return result;
    }
    result[0] = left;
    // 找到最后一个等于target的位置
    right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2; // 向上取整，避免死循环
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    result[1] = right;
    return result;
}

时间复杂度：O(logn)，其中n是数组的长度 空间复杂度：O(1)

6.4 搜索旋转排序数组（LeetCode 33）

题目描述：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值，则返回它的索引，否则返回 -1 。

示例：输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

解题思路：我们可以使用二分搜索来解决这个问题。关键在于确定目标值在旋转数组的哪一部分。

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        // 判断中间元素在左半部分还是右半部分
        if (nums[mid] >= nums[left]) {
            // 中间元素在左半部分（升序部分）
            if (target >= nums[left] && target < nums[mid]) {
                // 目标值在左半部分
                right = mid - 1;
            } else {
                // 目标值在右半部分
                left = mid + 1;
            }
        } else {
            // 中间元素在右半部分
            if (target > nums[mid] && target <= nums[right]) {
                // 目标值在右半部分
                left = mid + 1;
            } else {
                // 目标值在左半部分
                right = mid - 1;
            }
        }
    }
    return -1;
}

时间复杂度：O(logn)，其中n是数组的长度 空间复杂度：O(1)

七、高级搜索算法

7.1 深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。它的基本思想是：尽可能深地搜索树的分支，当节点的所有子节点都被访问过时，回溯到上一个节点，继续搜索其他分支。

算法步骤：

访问根节点
对根节点的每个子节点，递归地进行深度优先搜索

Java实现（二叉树的DFS）：

// 前序遍历（根-左-右）
public void dfsPreorder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 访问根节点
    System.out.print(root.val + " ");
    // 递归遍历左子树
    dfsPreorder(root.left);
    // 递归遍历右子树
    dfsPreorder(root.right);
}

// 中序遍历（左-根-右）
public void dfsInorder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 递归遍历左子树
    dfsInorder(root.left);
    // 访问根节点
    System.out.print(root.val + " ");
    // 递归遍历右子树
    dfsInorder(root.right);
}

// 后序遍历（左-右-根）
public void dfsPostorder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 递归遍历左子树
    dfsPostorder(root.left);
    // 递归遍历右子树
    dfsPostorder(root.right);
    // 访问根节点
    System.out.print(root.val + " ");
}

7.2 广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索树或图的算法。它的基本思想是：从根节点开始，逐层访问树的节点，先访问完当前层的所有节点，再访问下一层的节点。

算法步骤：

将根节点入队
当队列不为空时，执行以下操作： a. 出队一个节点 b. 访问该节点 c. 将该节点的所有子节点入队

Java实现（二叉树的BFS）：

public void bfs(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // 访问节点
        System.out.print(node.val + " ");
        // 将子节点入队
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

7.3 二分搜索树（BST）搜索

二分搜索树是一种特殊的二叉树，它的每个节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。利用这个特性，我们可以高效地在二分搜索树中查找元素。

算法步骤：

如果树为空，返回null
如果目标值等于根节点的值，返回根节点
如果目标值小于根节点的值，在左子树中递归查找
如果目标值大于根节点的值，在右子树中递归查找

Java实现：

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    if (val < root.val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
    }
}

八、排序与搜索的应用场景

8.1 排序算法的应用场景

数据查询：排序后可以使用二分搜索等高效的搜索算法
数据去重：排序后相同的元素会相邻，可以方便地去重
数据统计：排序后可以方便地统计数据的频率、中位数等
数据库索引：数据库中的索引通常使用B树或B+树等数据结构，它们都是基于排序的
负载均衡：在分布式系统中，排序可以用来实现负载均衡

8.2 搜索算法的应用场景

信息检索：搜索引擎使用各种搜索算法来快速查找相关信息
数据库查询：数据库使用索引和各种搜索算法来加速查询
路径规划：在地图应用中，使用搜索算法（如Dijkstra算法、A*算法）来规划最短路径
人工智能：在人工智能领域，搜索算法被广泛应用于问题求解、博弈等
网络爬虫：网络爬虫使用搜索算法来遍历和索引网页

九、排序与搜索的算法技巧总结

9.1 排序算法的选择

在实际应用中，我们需要根据数据的特点和需求来选择合适的排序算法：

数据量小：可以使用简单的排序算法，如插入排序、选择排序等
数据量中等：可以使用快速排序、归并排序等高效的排序算法
数据量很大：如果数据可以全部放入内存，可以使用快速排序、归并排序等；如果数据无法全部放入内存，需要使用外部排序算法
数据基本有序：可以使用插入排序、冒泡排序等，它们在这种情况下的时间复杂度接近O(n)
需要稳定排序：可以使用归并排序、插入排序、冒泡排序等稳定的排序算法
对空间复杂度有要求：可以使用原地排序算法，如快速排序、堆排序等

9.2 搜索算法的选择

在实际应用中，我们需要根据数据的特点和需求来选择合适的搜索算法：

数据无序：只能使用顺序搜索
数据有序：可以使用二分搜索、插值搜索等高效的搜索算法
数据结构是树：可以使用树搜索算法，如二叉搜索树搜索、平衡树搜索等
需要快速插入和查找：可以使用哈希搜索
图搜索：可以使用深度优先搜索、广度优先搜索等

9.3 常见的算法优化技巧

提前终止：在排序或搜索过程中，如果发现已经达到目标，可以提前终止算法
使用辅助数据结构：合理使用栈、队列、哈希表等辅助数据结构，可以优化算法的时间和空间复杂度
分治思想：将复杂的问题分解为简单的子问题，然后将子问题的解合并得到原问题的解
贪心思想：在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的
动态规划：将原问题分解为相对简单的子问题，先求解子问题，然后从这些子问题的解得到原问题的解

十、总结与展望

排序与搜索是计算机科学中最基础、最重要的算法之一，它们在计算机科学的各个领域都有广泛的应用。通过本文的学习，我们了解了各种排序算法和搜索算法的基本原理、实现方法和应用场景。

在实际应用中，我们需要根据数据的特点和需求来选择合适的排序和搜索算法。同时，我们也需要掌握一些常见的算法优化技巧，以提高算法的效率。

随着计算机科学的发展，排序与搜索算法也在不断地演进和优化。例如，在大数据时代，传统的排序和搜索算法已经无法满足需求，需要开发新的、适用于分布式环境的排序和搜索算法。此外，随着人工智能的发展，机器学习和深度学习技术也为排序和搜索算法带来了新的思路和方法。

通过不断地学习和实践，我们可以更好地理解和应用排序与搜索算法，为解决实际问题提供有力的支持。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除

数组

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！