当前位置：首页 > article >正文

Java中查找与排序算法探究

article 2024/11/6 15:26:29

二分查找

二分查找又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置
的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，
则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。代码如下

public class BinarySearch {
    // 二分查找方法
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出


            // 检查中间元素
            if (array[mid] == target) {
                return mid; // 找到目标元素，返回索引
            }

            // 如果目标大于中间元素，忽略左半边
            if (array[mid] < target) {
                left = mid + 1;
            } else { // 如果目标小于中间元素，忽略右半边
                right = mid - 1;
            }
        }

        return -1; // 未找到目标元素
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 6, 7, 11, 13, 15};
        int target = 7;

        int result = binarySearch(sortedArray, target);
        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引为: " + result);
        } else {
            System.out.println("元素 " + target + " 不在数组中。");
        }
    }
}

算法解析

int mid = left + (right - left) / 2;

基本概念

left：当前搜索范围的左边界索引。
right：当前搜索范围的右边界索引。
mid：当前搜索范围的中间索引。

防止溢出
在某些编程语言中（尤其是在处理大整数时），(left + right) 可能会超出整数的最大值，导致溢出。虽然在 Java 中这种情况不太常见，但在某些情况下（如大型数组和极端边界值）仍然可能发生。
为了防止这种情况，使用 left + (right - left) / 2。这个公式可以避免直接相加两个大数，而是先计算 right - left，再除以 2，最后加上 left。
公式拆解

right - left：是计算整个区间的长度
(right - left) / 2：找到当前区间长度的一半，这就是偏移量。
left +偏移量：将偏移量加到左边界上，就得到了中间位置。

时间复杂度和空间复杂度
时间复杂度：O(log n)

原因：二分查找每次将搜索区间缩小一半，因此它的时间复杂度是对数级别的。假设数组长度为 n，每一步操作后，区间缩小为原来的一半，所以最多需要进行 log₂n 次比较即可找到目标元素或确认元素不存在。

空间复杂度：O(1)

原因：二分查找只需要几个额外的变量（如 left、right、mid）来保存索引信息，不需要额外的存储空间与输入规模成比例增加，因此其空间复杂度是常数级别的。

冒泡排序

冒泡排序的工作原理：

它比较相邻的两个元素，如果它们的顺序错误就交换它们。
每一轮都能把当前未排序部分中最大的元素“冒泡”到正确的位置。
优化：如果某一轮没有发生任何交换，则说明数组已经排序好了，可以提前终止。

代码如下：

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {1, 9, 5, 3, 7, 18, 13, 15};
        System.out.println("排序前");
        printArray(arr);
        //冒泡排序思想  比较前后相邻两个数据  如果第一个个数据大于第二个数据 将这两个数据交换
        boolean swapped;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            swapped = false;
            for (int j = 0; j < length - i - 1; j++) {
                // 交换 arr[j] 和 arr[j+1]
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果没有发生交换，数组已经是有序的 跳出循环
            if (swapped == false) break;
        }
        System.out.println("排序后");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

算法解析
冒泡排序的思想主要通过两层遍历（循环）来实现，其中每一层循环分别代表不同的逻辑：

外层循环：
作用：控制整个排序过程进行的轮数。
具体说明：对于一个长度为 n 的数组，最多需要进行 n-1 轮比较（实际上可能会更少，如果提前检测到数组已经有序）。在每一轮中，将最大或最小的元素移动到未排序部分的末尾。
它确保每一轮结束后，至少有一个元素被放置在其最终位置。
内层循环：
作用：在当前轮次中，进行相邻元素的比较和交换。
具体说明：它在每一轮中逐个比较数组中的相邻元素，并根据需要交换它们，以确保当前未排序部分最大的元素“冒泡”到未排序部分的末尾。
每次遍历都会将未排序部分的最大值放到最后，从而逐步减少需要比较的元素数量。

时间复杂度和空间复杂度
时间复杂度：

最坏情况时间复杂度：O(n²)
在最坏的情况下（例如，数组是按降序排列的），冒泡排序需要进行 (n-1) 轮比较，每一轮都需要进行 (n-i-1) 次比较和交换操作（其中 (i) 是当前的轮次）。因此，总的比较和交换次数约为 ((n-1) + (n-2) + … + 1 = \frac{n(n-1)}{2})，这就是 O(n²)。
平均情况时间复杂度：O(n²)
在平均情况下，元素是随机分布的，冒泡排序仍然需要进行大量的比较和交换。平均下来，其时间复杂度仍为 O(n²)。
最好情况时间复杂度：O(n)
在最好的情况下（例如，数组已经是有序的），冒泡排序只需要进行一次遍历来确认数组是否已经排序。在这种情况下，只需进行 (n-1) 次比较，无需任何交换。因此时间复杂度为 O(n)。
空间复杂度

空间复杂度：O(1)
冒泡排序是一种原地排序算法，意味着它不需要额外的存储空间来存放临时数据（除了用于交换的一个临时变量）。因此，它的空间复杂度为 O(1)。

插入排序：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从
桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将
它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

如果输入数组已经是排好序的话，插入排序出现最佳情况，运行时间是输入规模的一个线性函数。
如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。

代码如下

public class InsertionSort {

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};

        System.out.println("未排序的数组：");
        printArray(array);

        insertionSort(array);

        System.out.println("\n已排序的数组：");
        printArray(array);
    }

    // 插入排序函数
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; ++i) {
            //待插入的数据
            int key = array[i];
            int j = i - 1;
            //此循环操作 将key与左边已经排好序的队列比对  将比key大的元素逐个向右移动  直到移动到最佳位置
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key; // 插入key到正确位置
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

算法解析

初始状态：
将第一个元素视为已经排序的序列，其余元素视为未排序的序列。
遍历未排序序列：
从第二个元素开始，依次将每个元素插入到前面已排好序的部分中。
插入过程：
对于每一个待插入的元素，从已排序部分的末尾开始向前扫描。
比较待插入元素与已排序元素，如果已排序元素比待插入元素大，则将其右移一位。
重复上述过程，直到找到一个不大于待插入元素的位置，将待插入元素放到该位置。
重复上述步骤：
依次处理剩余的未排序元素，直到整个数组有序。

举例说明
假设我们有一个数组 [12, 11, 13, 5, 6]，使用插入排序进行排序：
初始状态：[12] | [11, 13, 5, 6]

第一轮（i=1）：将 11 插入到 [12] 中：
比较 11 和 12，因为 11 < 12，所以交换位置。
数组变为 [11, 12] | [13, 5, 6]
第二轮（i=2）：将 13 插入到 [11, 12] 中：
13 > 12，直接追加到已排序部分。
数组变为 [11, 12, 13] | [5, 6]
第三轮（i=3）：将 5 插入到 [11, 12, 13] 中：
从后向前比较，发现 5 < 13, 5 < 12, 5 < 11。
将 5 插入到最前面。
数组变为 [5, 11, 12, 13] | [6]
第四轮（i=4）：将 6 插入到 [5, 11, 12, 13] 中：
从后向前比较，发现 6 < 13, 6 < 12, 6 > 5。
将 6 插入到 5 后面。

最终数组为 [5, 6, 11, 12, 13]

时间复杂度和空间复杂度

时间复杂度

最坏情况时间复杂度：O(n²)
在最坏情况下（例如，数组是按降序排列的），每个元素都需要与之前的所有元素进行比较和移动。对于第 (i) 个元素，这意味着需要进行 (i) 次比较。因此，总的比较和移动次数约为 (\frac{n(n-1)}{2})，这就是 O(n²)。
平均情况时间复杂度：O(n²)
在平均情况下，插入排序仍然需要进行大量的比较和移动，具体操作次数与最坏情况类似，因此平均时间复杂度也为 O(n²)。
最好情况时间复杂度：O(n)
在最好的情况下（例如，数组已经是有序的），每个元素只需与前一个元素比较一次即可确认其位置，无需移动。因此，只需进行 (n-1) 次比较，时间复杂度为 O(n)。

空间复杂度