Java中常见的查找算法与排序算法总结

Java中常见的查找算法与排序算法总结

在Java中，我们经常需要对数据进行查找和排序。这里我们总结了常见的查找算法和排序算法。

查找算法

1. 顺序查找

顺序查找也叫线性查找，它的思想是从数据序列的一端开始，逐个比较数据，直到找到满足条件的数据或者遍历完整个序列。

以下是Java代码示例：

public static int sequenceSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

2. 二分查找

二分查找也叫折半查找，它的思想是将有序数据序列分成若干个子序列，每次取中间位置的值与查找关键字进行比较，如果中间的值比查找的值大，则在左边子序列继续查找，否则在右边子序列继续查找，直到找到满足条件的值或者查找失败。

以下是Java代码示例：

public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = arr[mid];
        if (midVal < key) {
            low = mid + 1;
        } else if (midVal > key) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

排序算法

1. 冒泡排序

冒泡排序的思想是将相邻的两个数进行比较，如果顺序不对则进行交换，每次排序都会将最大（小）值移动到最后（前面）的位置。

以下是Java代码示例：

public static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 快速排序

快速排序的思想是以一个基准数为标准将数组分成小于和大于基准数两个子序列，对子序列分别进行递归排序，最后合并子序列得到最终结果。

以下是Java代码示例：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

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

以上就是Java中常见的查找算法和排序算法的总结。