使用Java实现数据结构和算法：排序、查找、图

r囧r小猫 2024-03-24 22:50 29阅读 0赞

> 如果您觉得本博客的内容对您有所帮助或启发，请关注我的博客，以便第一时间获取最新技术文章和教程。同时，也欢迎您在评论区留言，分享想法和建议。谢谢支持！

### 一、介绍 ###

数据结构和算法是计算机科学的两个基石，它们是解决各种复杂问题和优化计算机程序的关键工具。数据结构和算法的重要性体现在以下几个方面：

1.  **提高程序效率**：好的数据结构和算法可以让程序更快地运行，更有效地利用计算资源。例如，使用快速排序算法比使用冒泡排序算法可以大大减少排序时间。
2.  **解决复杂问题**：数据结构和算法可以帮助开发人员解决各种复杂问题，如图形处理、人工智能、大数据处理等。例如，使用适当的数据结构和算法可以使搜索引擎更好地处理用户查询，并返回最相关的结果。
3.  **提高程序可靠性**：使用正确的数据结构和算法可以避免程序运行时出现各种错误和异常。例如，在对数据进行操作时，如果使用了不适当的数据结构或算法，可能会导致数据损坏或程序崩溃。
4.  **更好地组织和管理数据**：使用正确的数据结构可以更好地组织和管理数据。例如，使用哈希表可以使程序更快地查找数据，而使用树结构可以更好地组织层次化数据。

数据结构和算法是计算机科学中非常重要的工具，可以提高程序效率、解决复杂问题、提高程序可靠性和更好地组织和管理数据。掌握数据结构和算法对于开发高质量、高效的计算机程序是非常必要的。

--------------------

### 二、排序算法 ###

#### 1、冒泡排序（Bubble Sort） ####

冒泡排序是一种基本的排序算法，它的思想是比较相邻的两个元素，如果前一个元素大于后一个元素，则交换这两个元素的位置，一轮比较后，最大的元素会被交换到数组的最后面。重复这个过程，直到整个数组都被排序。

以下是使用Java实现冒泡排序的代码：

import java.util.Arrays;
    
    public class BubbleSort {
        public static void bubbleSort(int[] arr) {
            int n = arr.length;
            // 外层循环控制比较轮数
            for (int i = 0; i < n - 1; i++) {
                // 内层循环控制每轮比较次数
                for (int j = 0; j < n - i - 1; j++) {
                    // 如果前一个元素大于后一个元素，则交换位置
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            int[] arr = { 4, 2, 8, 3, 1, 9, 6, 5, 7 };
            bubbleSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

在上面的代码中，我们定义了一个静态方法`bubbleSort`来实现冒泡排序，它接受一个整型数组作为参数，用两个循环来实现冒泡排序的过程。在外层循环中，控制比较的轮数，循环次数为数组长度减1；在内层循环中，控制每轮比较的次数，循环次数为数组长度减去当前轮数减1。如果前一个元素大于后一个元素，则交换这两个元素的位置。

最后，在`main`方法中调用`bubbleSort`方法对一个整型数组进行排序，并使用`Arrays.toString`方法将排序后的结果输出到控制台。

#### 2、选择排序（Selection Sort） ####

选择排序的思想是从数组中选择最小的元素，将其放在数组的最前面，然后从剩余的元素中再选择最小的元素，放在已排序部分的最后面。重复这个过程，直到整个数组都被排序。

以下是使用Java实现选择排序的代码：

import java.util.Arrays;
    
    public class SelectionSort {
        public static void selectionSort(int[] arr) {
            int n = arr.length;
            // 外层循环控制已排序部分的长度
            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;
                    }
                }
                // 将最小元素与已排序部分的末尾元素交换位置
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    
        public static void main(String[] args) {
            int[] arr = { 4, 2, 8, 3, 1, 9, 6, 5, 7 };
            selectionSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

在上面的代码中，我们定义了一个静态方法`selectionSort`来实现选择排序，它接受一个整型数组作为参数，用两个循环来实现选择排序的过程。在外层循环中，控制已排序部分的长度，循环次数为数组长度减1；在内层循环中，从未排序部分中选出最小元素的下标。如果找到了一个更小的元素，则将其下标更新为最小元素的下标。

最后，在`main`方法中调用`selectionSort`方法对一个整型数组进行排序，并使用`Arrays.toString`方法将排序后的结果输出到控制台。

#### 3、插入排序（Insertion Sort） ####

插入排序的思想是将数组分为已排序和未排序两部分，每次将未排序的元素插入到已排序部分的适当位置。具体操作是从未排序部分取出第一个元素，从已排序部分的最后一个元素开始向前比较，直到找到比它小的元素为止，然后将该元素插入到合适位置。

以下是使用Java实现插入排序的代码：

import java.util.Arrays;
    
    public class InsertionSort {
        public static void insertionSort(int[] arr) {
            int n = arr.length;
            // 外层循环控制已排序部分的长度
            for (int i = 1; i < n; i++) {
                int cur = arr[i];
                int j = i - 1;
                // 内层循环将待排序元素插入到已排序部分的适当位置
                while (j >= 0 && arr[j] > cur) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = cur;
            }
        }
    
        public static void main(String[] args) {
            int[] arr = { 4, 2, 8, 3, 1, 9, 6, 5, 7 };
            insertionSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

在上面的代码中，我们定义了一个静态方法`insertionSort`来实现插入排序，它接受一个整型数组作为参数，用两个循环来实现插入排序的过程。在外层循环中，控制已排序部分的长度，循环次数为数组长度减1；在内层循环中，将待排序元素插入到已排序部分的适当位置。将待排序元素与已排序部分中的元素从后往前依次比较，如果已排序部分中的元素比待排序元素大，则将该元素向后移动一个位置，直到找到待排序元素的正确位置。

最后，在`main`方法中调用`insertionSort`方法对一个整型数组进行排序，并使用`Arrays.toString`方法将排序后的结果输出到控制台。

#### 4、快速排序（Quick Sort） ####

快速排序是一种分治思想的排序算法，它的核心思想是将数组分成两部分，一部分比另一部分小，然后对这两部分分别进行快速排序，最后合并起来。具体操作是选择一个基准元素，将数组分成两部分，左边是比基准元素小的元素，右边是比基准元素大的元素，然后递归地对左右两部分进行快速排序。

快速排序是一种高效的排序算法，它的基本思想是选定一个基准元素，将待排序部分分成左右两个子序列，使得左子序列中的元素都小于基准元素，右子序列中的元素都大于等于基准元素。然后对左右子序列递归地进行快速排序，直到整个序列都有序。

以下是使用Java实现快速排序的代码：

import java.util.Arrays;
    
    public class QuickSort {
        public static void quickSort(int[] arr, int left, int right) {
            if (left < right) {
                // 找到基准元素的位置
                int pivotIndex = partition(arr, left, right);
                // 对左右子序列递归地进行快速排序
                quickSort(arr, left, pivotIndex - 1);
                quickSort(arr, pivotIndex + 1, right);
            }
        }
    
        private static int partition(int[] arr, int left, int right) {
            // 将第一个元素作为基准元素
            int pivot = arr[left];
            int i = left + 1;
            int j = right;
            while (true) {
                // 从左往右找到第一个大于等于基准元素的位置
                while (i <= j && arr[i] < pivot) {
                    i++;
                }
                // 从右往左找到第一个小于基准元素的位置
                while (i <= j && arr[j] >= pivot) {
                    j--;
                }
                if (i >= j) {
                    // 如果i >= j，则说明已经将数组分成了左右两个子序列
                    // 左子序列中的元素都小于基准元素，右子序列中的元素都大于等于基准元素
                    break;
                }
                // 交换arr[i]和arr[j]的位置，将小于等于基准元素的元素放到左子序列中
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                // 继续在左子序列中找大于等于基准元素的元素
                i++;
                // 在右子序列中找小于基准元素的元素
                j--;
            }
            // 将基准元素放到正确的位置，即i-1的位置
            arr[left] = arr[i - 1];
            arr[i - 1] = pivot;
            // 返回基准元素的位置
            return i - 1;
        }
    
        public static void main(String[] args) {
            int[] arr = { 4, 2, 8, 3, 1, 9, 6, 5, 7 };
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    }

在上面的代码中，我们定义了一个静态方法`quickSort`来实现快速排序，它接受一个整型数组、左边界和右边界作为参数，用递归的方式实现快速排序的过程。在每一轮快速排序中，我们首先选定一个基准元素，然后使用两个指针i和j，分别指向左右两端。然后，我们从左往右遍历数组，找到第一个大于等于基准元素的元素的位置i，再从右往左遍历数组，找到第一个小于基准元素的元素的位置j。如果i和j没有相遇，就交换arr\[i\]和arr\[j\]的位置，将小于等于基准元素的元素放到左子序列中。继续在左子序列中找大于等于基准元素的元素，直到i >= j，说明已经将数组分成了左右两个子序列。然后，将基准元素放到正确的位置，即i-1的位置，左子序列中的元素都小于基准元素，右子序列中的元素都大于等于基准元素。

快速排序的时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)，但是这种情况比较少见。它的空间复杂度为O(logn)，它是原地排序算法，不需要额外的空间。

下面是使用上面的代码对一个整型数组进行快速排序的示例输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

#### 5、归并排序（Merge Sort） ####

归并排序是一种基于分治思想的排序算法，它的核心思想是将一个大问题分解成若干个小问题进行解决，然后将小问题的解合并起来，得到原问题的解。归并排序的基本思路是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列之间进行合并，得到完全有序的序列。

归并排序适用于大规模数据的排序，其时间复杂度稳定在O(nlogn)。它的主要优点是稳定性好，可以处理大规模数据，但是它需要额外的空间来存储分治时产生的中间结果。

下面是使用Java实现归并排序的示例代码：

import java.util.Arrays;
    
    public class MergeSort {
    
        public static void mergeSort(int[] arr) {
            int[] temp = new int[arr.length];
            sort(arr, 0, arr.length - 1, temp);
        }
    
        private static void sort(int[] arr, int left, int right, int[] temp) {
            if (left < right) {
                int mid = (left + right) / 2;
                sort(arr, left, mid, temp);
                sort(arr, mid + 1, right, temp);
                merge(arr, left, mid, right, temp);
            }
        }
    
        private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
            int i = left;
            int j = mid + 1;
            int k = 0;
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            k = 0;
            while (left <= right) {
                arr[left++] = temp[k++];
            }
        }
    
        public static void main(String[] args) {
            int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            mergeSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

在归并排序中，最重要的步骤就是合并两个有序子序列。当我们在合并两个有序子序列时，我们可以通过双指针遍历的方式，将两个子序列中的元素按照大小依次放入一个临时数组中，直到其中一个子序列的元素全部被放入临时数组中。此时，另一个子序列中的元素肯定都比临时数组中的元素大（因为它们是有序的），因此我们可以直接将这些元素放到临时数组的末尾。

最后，我们只需要将临时数组中的元素复制回原数组中，这样就完成了归并排序的整个过程。

在实际应用中，归并排序常常被用作内部排序算法，例如Java中的Arrays.sort方法就是使用了归并排序。

#### 6、堆排序（Heap sort） ####

堆排序是一种基于堆数据结构的排序算法，它的思想是先将待排序的数组构建成一个二叉堆，然后依次将堆顶元素（即最大或最小元素）取出，放到已排序部分的末尾，然后重新调整剩余元素的堆结构，使之满足堆的性质。重复这个过程，直到所有元素都被排序。

堆排序可以分为两个步骤：

1.  构建堆：将待排序的数组构建成一个二叉堆。具体操作是从数组的最后一个非叶子节点开始，依次将其与其子节点进行比较，如果不满足堆的性质，则交换两个节点的位置，然后向前移动，继续比较，直到根节点。
2.  排序：依次将堆顶元素取出，放到已排序部分的末尾，然后重新调整剩余元素的堆结构，使之满足堆的性质。具体操作是将堆顶元素和堆的最后一个元素交换位置，然后将堆的大小减1，再对堆顶元素进行下滤操作，将其移动到合适的位置，使之满足堆的性质。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，它是一种原地排序算法，不需要额外的空间存储数据。堆排序适用于需要排序大量数据且对空间复杂度有限制的场景，但由于堆排序的常数较大，相比于快速排序等算法，在小规模数据上的效率可能不如其他算法。

下面是一个使用Java实现的堆排序的例子：

import java.util.Arrays;
    
    public class HeapSort {
        public static void sort(int[] arr) {
            int n = arr.length;
            
            // 构建堆
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(arr, n, i);
            }
    
            // 堆排序
            for (int i = n - 1; i >= 0; i--) {
                // 将堆顶元素与末尾元素交换
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
    
                // 对剩余元素重新构建堆
                heapify(arr, i, 0);
            }
        }
    
        // 堆化操作
        private static void heapify(int[] arr, int n, int i) {
            int largest = i; // 初始化最大值为根节点
            int l = 2 * i + 1; // 左孩子节点
            int r = 2 * i + 2; // 右孩子节点
    
            // 找出三个节点中的最大值
            if (l < n && arr[l] > arr[largest]) {
                largest = l;
            }
            if (r < n && arr[r] > arr[largest]) {
                largest = r;
            }
    
            // 如果最大值不是根节点，则交换根节点和最大值，并继续向下堆化
            if (largest != i) {
                int temp = arr[i];
                arr[i] = arr[largest];
                arr[largest] = temp;
                heapify(arr, n, largest);
            }
        }
        
        public static void main(String[] args) {
            int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

在这个例子中，我们先使用`heapify`方法将数组构建成一个最大堆，然后在每一轮排序中将堆顶元素和数组末尾元素交换位置，并重新构建堆。最终，我们就可以得到一个有序的数组。由于堆排序的时间复杂度为O(nlogn)，因此它是一种非常高效的排序算法，常常被用于大规模数据的排序。

#### 7、小结 ####

冒泡排序和选择排序是最简单的排序算法，虽然它们的时间复杂度较高，但是它们易于理解和实现。插入排序的时间复杂度略低于冒泡排序和选择排序，但是由于它具有稳定性和较好的性能，因此它在实际应用中比较常见。

快速排序和归并排序是更高效的排序算法，它们的时间复杂度为O(nlogn)，因此它们在处理大规模数据时具有优势。快速排序通常比归并排序更快，但是它的稳定性较差。相比之下，归并排序的稳定性较好，适用于更多的场景。

堆排序是一种时间复杂度为O(nlogn)的排序算法，它的性能比冒泡排序、选择排序和插入排序都要好，但是在实际应用中常常被归并排序和快速排序所取代。

在实际应用中，我们需要根据具体的问题和数据特征选择不同的排序算法。对于小规模数据，我们可以使用冒泡排序、选择排序、插入排序等简单的排序算法；对于大规模数据，我们可以使用快速排序、归并排序、堆排序等更高效的排序算法。

--------------------

### 三、查找算法 ###

#### 1、线性查找 ####

线性查找，也称为顺序查找，是一种基本的查找算法。它的思路是从数据集合的第一个元素开始逐个向后查找，直到找到目标元素或遍历完整个数据集合为止。因为是逐个比较，所以适用于各种数据类型，包括无序和有序的数据集合。

线性查找的时间复杂度为 O(n)，其中 n 表示数据集合的大小，最坏情况下需要查找整个数据集合。但如果数据集合有序，可以通过优化跳出循环来减少比较次数，此时时间复杂度可达到 O(1)。

以下是使用 Java 实现线性查找的示例代码：

public class LinearSearch {
        public static int linearSearch(int[] arr, int target) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == target) {
                    return i;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            int target = 3;
            int index = linearSearch(arr, target);
            if (index != -1) {
                System.out.println("目标元素 " + target + " 在数组中的位置为：" + index);
            } else {
                System.out.println("目标元素 " + target + " 不在数组中");
            }
        }
    }

![d8ccce366ce5fac4f2e56a3efce18034.png][]

上面的代码实现了一个简单的线性查找函数 `linearSearch`，并在 `main` 函数中演示了如何使用该函数查找数组中的元素。

#### 2、二分查找 ####

二分查找，也称为折半查找，是一种常用的查找算法。它的思路是针对有序的数据集合，在每次查找过程中都将待查找区间缩小一半，直到找到目标元素或者待查找区间为空为止。

二分查找的时间复杂度为 O(log n)，其中 n 表示数据集合的大小。由于每次查找都会将待查找区间缩小一半，因此它的效率比线性查找高很多，特别是对于大型有序数据集合。但是它的局限性也很明显，只适用于有序数据集合。

以下是使用 Java 实现二分查找的示例代码：

public class BinarySearch {
        public static int binarySearch(int[] arr, int target) {
            int left = 0;
            int right = arr.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] == target) {
                    return mid;
                } else if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            int target = 3;
            int index = binarySearch(arr, target);
            if (index != -1) {
                System.out.println("目标元素 " + target + " 在数组中的位置为：" + index);
            } else {
                System.out.println("目标元素 " + target + " 不在数组中");
            }
        }
    }

上面的代码实现了一个简单的二分查找函数 `binarySearch`，并在 `main` 函数中演示了如何使用该函数查找数组中的元素。

![aa9170b3e459e3d80e609ffa4c747c55.png][]

#### 3、插值查找 ####

插值查找是二分查找的一种变体，也适用于有序数据集。与二分查找不同的是，插值查找根据目标值的估计位置来选择查找区间，而不是直接选择中间位置。

具体而言，插值查找算法的基本思想是将目标值与查找区间的两个端点相比较，然后根据目标值在整个数据集中的相对位置，计算出一个估计位置。接着，根据该估计位置来缩小查找区间，直到找到目标值为止。

插值查找算法的时间复杂度为O(logn)，但是对于数据分布比较均匀的数据集，插值查找的效率可能会比二分查找更高。但是对于极端数据分布情况，插值查找的性能可能会下降。

下面是插值查找的Java代码实现示例：

public class InterpolationSearch {
        public static int interpolationSearch(int[] arr, int target) {
            int left = 0, right = arr.length - 1;
            while (left <= right && target >= arr[left] && target <= arr[right]) {
                int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);
                if (arr[pos] == target) {
                    return pos;
                }
                if (arr[pos] < target) {
                    left = pos + 1;
                } else {
                    right = pos - 1;
                }
            }
            return -1;
        }
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            int target = 5;
            int index = interpolationSearch(arr, target);
            if (index != -1) {
                System.out.println("目标元素 " + target + " 在数组中的位置为：" + index);
            } else {
                System.out.println("目标元素 " + target + " 不在数组中");
            }
        }
    }

在该示例中，我们首先计算出估计位置pos，然后根据pos与target的大小关系来缩小查找范围。具体而言，如果arr\[pos\] < target，则将left赋值为pos + 1；如果arr\[pos\] > target，则将right赋值为pos - 1。如果arr\[pos\] = target，则返回pos。

![e142bc496167061d643027026800bc16.png][]

#### 4、斐波那契查找 ####

斐波那契查找是一种基于黄金分割点的查找算法，可以用于有序数据集的查找。与二分查找类似，斐波那契查找也是将目标值与查找区间的中间点进行比较，然后根据比较结果来缩小查找范围。

不同的是，斐波那契查找使用了黄金分割点的概念，即将查找区间按照一定比例分成两个子区间。具体而言，假设查找区间的长度为n，我们先在斐波那契数列中找到一个比n大且最接近n的数f，然后将查找区间分成长度为f和f-1的两个子区间。接着，将目标值与两个子区间的中间点进行比较，然后根据比较结果来进一步缩小查找范围。

斐波那契查找算法的时间复杂度为O(logn)，但是相对于二分查找，它需要额外的空间来存储斐波那契数列。

斐波那契查找适用于有序数据集，且数据集长度不确定或数据集分布较为均匀的情况。由于斐波那契数列的增长速度比二分查找快，因此在查找区间长度比较大的情况下，斐波那契查找的效率可能会更高。

下面是斐波那契查找的Java代码实现示例：

public class FibonacciSearch {
        public static int fibonacciSearch(int[] arr, int target) {
            int n = arr.length;
            int fibMinus2 = 0, fibMinus1 = 1, fib = fibMinus2 + fibMinus1;
            while (fib < n) {
                fibMinus2 = fibMinus1;
                fibMinus1 = fib;
                fib = fibMinus2 + fibMinus1;
            }
            int offset = -1;
            while (fib > 1) {
                int i = Math.min(offset + fibMinus2, n - 1);
                if (arr[i] < target) {
                    fib = fibMinus1;
                    fibMinus1 = fibMinus2;
                    fibMinus2 = fib - fibMinus1;
                    offset = i;
                } else if (arr[i] > target) {
                    fib = fibMinus2;
                    fibMinus1 -= fibMinus2;
                    fibMinus2 = fib - fibMinus1;
                } else {
                    return i;
                }
            }
            if (fibMinus1 == 1 && arr[offset + 1] == target) {
                return offset + 1;
            }
            return -1;
        }
        public static void main(String[] args) {
            int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
            int target = 7;
            int index = fibonacciSearch(arr, target);
            if (index != -1) {
                System.out.println("目标元素" + target + "的下标为" + index);
            } else {
                System.out.println("未找到目标元素" + target);
            }
        }
    }

在该示例中，我们先使用斐波那契数列来计算查找区间的长度，然后在查找区间中查找目标值。具体而言，我们首先找到比目标值大且最接近查找区间长度的斐波那契数f，然后将查找区间分成长度为f和f-1的两个子区间。接着，使用while循环进行迭代查找，直到找到目标值或者查找区间长度为1时停止查找。

在每一轮迭代中，我们计算中间点的下标i，然后将目标值与arr\[i\]进行比较。如果目标值小于arr\[i\]，则将查找区间缩小到左边的子区间，否则将查找区间缩小到右边的子区间。最后，当查找区间长度为1时，如果arr\[offset+1\]等于目标值，则返回offset+1，否则返回-1表示查找失败。

下面是使用斐波那契查找算法查找一个有序数组中的元素的示例：

int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int index = fibonacciSearch(arr, target);
    if (index != -1) {
        System.out.println("目标元素" + target + "的下标为" + index);
    } else {
        System.out.println("未找到目标元素" + target);
    }

输出结果为：

![5eb611243758deba42284bf1e28b738c.png][]

可以看到，使用斐波那契查找算法可以快速地在有序数组中查找目标元素的下标。

#### 5、哈希查找 ####

哈希查找，也称为散列表查找，是一种基于哈希表的查找算法。在哈希表中，我们将关键字映射到一个固定的位置上，称为哈希地址，这样就可以在O(1)的时间复杂度内快速查找到目标元素。

哈希查找的应用场景比较广泛，例如数据库中的索引、编译器中的符号表、缓存系统等。由于哈希表具有快速查找、插入、删除等特点，因此在需要频繁进行数据操作的场景中，使用哈希查找可以大大提高程序的性能。

哈希查找的时间复杂度为O(1)，但是在处理哈希冲突时可能会影响查找效率。常见的解决哈希冲突的方法包括链地址法、开放地址法等。

下面是使用哈希查找算法查找一个数组中的元素的示例：

import java.util.HashMap;
    import java.util.Map;
    
    public class HashSearch {
        public static int hashSearch(int[] arr, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                map.put(arr[i], i);
            }
            if (map.containsKey(target)) {
                return map.get(target);
            } else {
                return -1;
            }
        }
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            int target = 5;
            int index = hashSearch(arr, target);
            if (index != -1) {
                System.out.println("目标元素 " + target + " 在数组中的位置为：" + index);
            } else {
                System.out.println("目标元素 " + target + " 不在数组中");
            }
        }
    }

在上述代码中，我们使用Java中的HashMap来实现哈希表，并将数组中的元素作为键，元素的下标作为值。然后我们只需要在哈希表中查找目标元素，如果存在则返回其下标，否则返回-1表示查找失败。

![c2e16f01ed43b59d9ee3218ecf8fe895.png][]

需要注意的是，在使用哈希表实现哈希查找时，我们需要选择合适的哈希函数来保证元素在哈希表中分布均匀，从而避免哈希冲突的发生。

#### 6、树查找 ####

常见的树查找包括二叉查找树、平衡二叉树、B树、B+树和红黑树。这些树结构都具有良好的查找性能，各自适用于不同的应用场景。

*  二叉查找树（Binary Search Tree，BST）：是一种特殊的二叉树，它满足任意节点的左子树都小于该节点，右子树都大于该节点。在二叉查找树中，查找、插入、删除等操作的时间复杂度为 O(log n)。
 *  平衡二叉树：如AVL树、红黑树等，它们能够保证树的左右两边高度相差不超过1，从而保证了查找、插入、删除等操作的时间复杂度为 O(log n)。
 *  B树：是一种多路平衡查找树，它的每个节点有多个子节点，可以存储多个数据项。B树通常应用于外部存储器中，如磁盘等，因为其节点可以存储多个数据项，能够有效地减少磁盘I/O操作次数，提高数据读取速度。
 *  B+树：是在B树基础上进行的改进，与B树相比，B+树的内部节点不存储数据，只存储索引信息，所有的数据都存储在叶子节点中。B+树也通常应用于外部存储器中，能够更加高效地利用磁盘空间。
 *  红黑树：是一种自平衡的二叉查找树，它通过对节点进行染色，保证了树的高度近似平衡，从而保证了查找、插入、删除等操作的时间复杂度为 O(log n)。红黑树常用于编程语言中的内置数据结构，如C++ STL中的set、map等。

##### 二叉查找树 #####

二叉查找树是一种常用的数据结构，它是一棵二叉树，其中每个节点都包含一个键值和对应的值。对于每个节点，其左子树中的所有节点的键值均小于该节点的键值，右子树中的所有节点的键值均大于该节点的键值。通过这种方式，我们可以使用二叉查找树来快速查找、插入和删除元素。

二叉查找树的时间复杂度与树的高度相关，最坏情况下可能退化成链表，时间复杂度变成O(n)。因此，为了避免这种情况，我们可以使用平衡二叉树或者其他更高级的数据结构来代替二叉查找树。

下面是一个使用Java实现的二叉查找树示例：

class Node {
        int key;
        int value;
        Node left;
        Node right;
    
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
    
    class BST {
        private Node root;
    
        public BST() {
            root = null;
        }
    
        public int get(int key) {
            Node node = get(root, key);
            return node == null ? -1 : node.value;
        }
    
        private Node get(Node node, int key) {
            if (node == null) {
                return null;
            }
            if (node.key == key) {
                return node;
            } else if (node.key > key) {
                return get(node.left, key);
            } else {
                return get(node.right, key);
            }
        }
    
        public void put(int key, int value) {
            root = put(root, key, value);
        }
    
        private Node put(Node node, int key, int value) {
            if (node == null) {
                return new Node(key, value);
            }
            if (node.key == key) {
                node.value = value;
            } else if (node.key > key) {
                node.left = put(node.left, key, value);
            } else {
                node.right = put(node.right, key, value);
            }
            return node;
        }
    }

在实际应用中，我们需要根据数据特征和具体需求选择不同的查找算法。对于有序数据集，二分查找和树查找是比较常见的选择；对于无序数据集，线性查找和哈希查找是比较常见的选择。此外，在处理大规模数据时，哈希查找和树查找通常具有更好的性能。

--------------------

### 四、图的表示和遍历 ###

#### 1、图的基本概念和定义 ####

图是由节点（vertex）和边（edge）组成的一种数据结构，通常用于描述事物之间的关系。一个图可以用G=(V,E)表示，其中V表示节点的集合，E表示边的集合。每个边连接着两个节点，这两个节点可以是相同的节点（自环），也可以是不同的节点（非自环）。

图可以分为有向图和无向图两种类型。有向图中的边有方向，表示从一个节点指向另一个节点，而无向图中的边没有方向，表示两个节点之间的关系是相互的。

图中的节点可以有权重（weight），表示节点之间的关系有强弱之分，例如，社交网络中的用户之间有好友关系，好友数量就是权重。

图中有一些基本的概念，包括度（degree）、路径（path）、连通性（connectivity）、生成树（spanning tree）等。

*  度：节点的度是指与该节点相连的边的数量。
 *  路径：路径是由边连接的节点序列，路径的长度是指路径中边的数量。
 *  连通性：一个无向图中的两个节点如果有路径相连，则这两个节点是连通的。如果一个有向图中的节点能够到达另一个节点，则这两个节点是连通的。
 *  生成树：一个无向图的生成树是指该图的一个连通子图，且包含图中所有节点，但不包含任何回路（cycle），且边的数量最少。对于有向图，生成树的定义需要区分入度（indegree）和出度（outdegree）。

图在计算机科学中有广泛的应用，包括网络拓扑结构、图像处理、自然语言处理等领域。

#### 2、图的表示方法 ####

图可以使用多种方式进行表示，常见的三种表示方法如下：

1.  邻接矩阵（Adjacency Matrix）：使用二维数组表示图中的节点和边，其中数组的行和列表示节点，如果两个节点之间存在一条边，则在对应的行和列上标记为1或者边的权值。如果两个节点之间不存在边，则在对应的位置标记为0。
2.  邻接表（Adjacency List）：使用一个数组来表示所有的节点，每个节点对应一个链表，链表中存储该节点所连接的其他节点以及对应的边的权值。
3.  关联矩阵（Incidence Matrix）：使用一个二维数组表示图中的节点和边，其中数组的行表示节点，列表示边。如果节点和边之间存在关联，则在对应的位置标记为1或者边的权值，否则标记为0。

在实际应用中，选择不同的表示方法会影响算法的时间和空间复杂度。比如，邻接矩阵适合表示边稠密的图，但是空间复杂度较高；邻接表适合表示边稀疏的图，但是访问节点的时间复杂度较高。

##### 邻接矩阵（Adjacency Matrix） #####

邻接矩阵是图的一种常见表示方法，用一个二维数组表示所有节点之间的连接关系。如果节点 i 与节点 j 之间存在一条边，则邻接矩阵的第 i 行第 j 列为 1；否则为 0。

邻接矩阵适用于稠密图，即边数接近于节点数的图。由于每条边需要占用一个矩阵元素，因此对于边数较少的稀疏图，使用邻接矩阵会造成大量的空间浪费。此外，邻接矩阵不能很好地支持图的动态增删边操作，因为在增删边时需要重新调整矩阵大小，导致时间复杂度较高。

邻接矩阵的优点在于：

*  可以快速判断任意两个节点之间是否有边相连；
 *  支持常数时间的随机访问节点。

以下是一个使用邻接矩阵表示的有向图的Java代码示例：

public class DirectedGraph {
        private int V; // 图中节点的数量
        private int[][] adjMatrix; // 邻接矩阵
    
        public DirectedGraph(int V) {
            this.V = V;
            this.adjMatrix = new int[V][V];
        }
    
        // 添加一条边
        public void addEdge(int source, int destination) {
            adjMatrix[source][destination] = 1;
        }
    
        // 打印邻接矩阵
        public void printAdjMatrix() {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    System.out.print(adjMatrix[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            DirectedGraph graph = new DirectedGraph(4);
            graph.addEdge(0, 1);
            graph.addEdge(0, 2);
            graph.addEdge(1, 2);
            graph.addEdge(2, 0);
            graph.addEdge(2, 3);
            graph.addEdge(3, 3);
    
            graph.printAdjMatrix();
        }
    }

运行上述代码将输出以下邻接矩阵：

0 1 1 0 
    0 0 1 0 
    1 0 0 1 
    0 0 0 1

该邻接矩阵表示的有向图包含四个节点，分别是0、1、2、3。其中节点0有两条出边，分别指向节点1和节点2；节点1有一条出边指向节点2；节点2有两条出边，分别指向节点0和节点3；节点3没有出边。

##### 邻接表（Adjacency List） #####

邻接表是图的另一种常见的表示方法，它使用链表来表示图中每个节点的邻居节点。每个节点都有一个链表，链表中包含该节点的所有邻居节点。

下面是邻接表的Java代码实现：

首先定义一个邻接表节点类 `AdjListNode`，它包含一个节点编号 `v` 和一个指向下一个邻居节点的指针 `next`。

class AdjListNode {
        int v;
        AdjListNode next;
    
        public AdjListNode(int v) {
            this.v = v;
            next = null;
        }
    }

然后定义一个邻接表类 `AdjList`，它包含一个数组 `adjLists`，数组中每个元素都是一个邻接表节点，表示图中的一个节点和它的邻居节点。

class AdjList {
        AdjListNode[] adjLists;
    
        public AdjList(int numVertices) {
            adjLists = new AdjListNode[numVertices];
    
            for (int i = 0; i < numVertices; i++) {
                adjLists[i] = new AdjListNode(i);
            }
        }
    
        // 添加一条边，连接节点u和节点v
        public void addEdge(int u, int v) {
            AdjListNode newNode = new AdjListNode(v);
            newNode.next = adjLists[u].next;
            adjLists[u].next = newNode;
        }
    }

使用邻接表表示一个无向图的例子：

0
         / 
        1 - 2
       / \   \
      3   4   5

对应的Java代码：

// 创建一个有6个节点的邻接表
    AdjList adjList = new AdjList(6);
    
    // 添加边
    adjList.addEdge(0, 1);
    adjList.addEdge(1, 0);
    adjList.addEdge(1, 2);
    adjList.addEdge(2, 1);
    adjList.addEdge(1, 3);
    adjList.addEdge(3, 1);
    adjList.addEdge(1, 4);
    adjList.addEdge(4, 1);
    adjList.addEdge(2, 5);
    adjList.addEdge(5, 2);

邻接表的优点是可以用较少的空间表示稀疏图，但它的缺点是在查找某个节点的所有邻居节点时需要遍历链表，时间复杂度为 $O(k)$，其中 $k$ 是节点的平均度数。因此，在需要频繁查找节点的邻居节点时，邻接矩阵更为高效。

##### 关联矩阵（Incidence Matrix） #####

关联矩阵是一种图的表示方法，其中行代表顶点，列代表边，每个元素表示该顶点是否与该边相连。如果一个顶点与一条边相连，则在该元素上显示1，否则显示0。

下面是一个简单的关联矩阵的例子，其中有4个顶点和5条边：

a b c d e
    a   1 0 0 1 1
    b   0 1 1 1 0
    c   0 0 1 0 1
    d   1 1 0 0 0

在Java中，我们可以使用二维数组来实现关联矩阵。下面是一个用Java实现的简单的关联矩阵示例代码：

public class AdjacencyMatrix {
        private int[][] matrix; // 二维数组来存储邻接矩阵
        private int numVertices; // 图中的顶点数
        private int numEdges; // 图中的边数
    
        // 构造方法，初始化邻接矩阵
        public AdjacencyMatrix(int numVertices) {
            this.numVertices = numVertices;
            this.numEdges = 0;
            matrix = new int[numVertices][numVertices];
            for (int i = 0; i < numVertices; i++) {
                for (int j = 0; j < numVertices; j++) {
                    matrix[i][j] = 0; // 初始时将所有元素置为0
                }
            }
        }
    
        // 添加边的方法
        public void addEdge(int i, int j) {
            if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
                matrix[i][j] = 1; // 将矩阵对应位置上的元素置为1
                matrix[j][i] = 1; // 因为是无向图，所以需要将两个位置都置为1
                numEdges++; // 边的数量加1
            }
        }
    
        // 获取顶点数
        public int getNumVertices() {
            return numVertices;
        }
    
        // 获取边数
        public int getNumEdges() {
            return numEdges;
        }
    
        // 获取某个位置的元素
        public int get(int i, int j) {
            if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
                return matrix[i][j];
            } else {
                return -1;
            }
        }
    
        // 打印邻接矩阵
        public void printMatrix() {
            for (int i = 0; i < numVertices; i++) {
                for (int j = 0; j < numVertices; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

#### 3、深度优先搜索算法 ####

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。该算法从一个根节点开始探索它的所有分支，直到没有未探索的节点为止，然后回溯到前一个节点，再探索其他分支。DFS 常用递归实现。

下面是一个基于邻接表的图的深度优先搜索算法的 Java 实现：

import java.util.*;
    
    public class Graph {
        private int V; // 图的顶点数
        private LinkedList<Integer> adj[]; // 邻接表表示图
    
        // 构造函数，初始化邻接表
        public Graph(int v) {
            V = v;
            adj = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new LinkedList();
            }
        }
    
        // 添加一条边，连接节点 v 和 w
        void addEdge(int v, int w) {
            adj[v].add(w);
        }
    
        // 深度优先搜索
        void DFSUtil(int v, boolean visited[]) {
            visited[v] = true;
            System.out.print(v + " ");
    
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n])
                    DFSUtil(n, visited);
            }
        }
    
        // 从指定的节点开始进行深度优先搜索
        void DFS(int v) {
            boolean visited[] = new boolean[V];
            DFSUtil(v, visited);
        }
    
        public static void main(String args[]) {
            Graph g = new Graph(4);
    
            g.addEdge(0, 1);
            g.addEdge(0, 2);
            g.addEdge(1, 2);
            g.addEdge(2, 0);
            g.addEdge(2, 3);
            g.addEdge(3, 3);
    
            System.out.println("从节点 2 开始的深度优先搜索结果为：");
            g.DFS(2);
        }
    }

输出：

从节点 2 开始的深度优先搜索结果为：
    2 0 1 3

在上述代码中，我们首先定义了一个 Graph 类，其中包含了图的顶点数 `V` 和一个邻接表 `adj`，用于表示图的结构。然后我们定义了 `addEdge` 方法，用于向图中添加一条边。接着我们实现了 `DFSUtil` 方法，用于进行深度优先搜索。其中，我们使用了一个 `visited` 数组来记录每个节点是否被访问过，并使用 `Iterator` 迭代器遍历与当前节点相邻的节点。最后，我们实现了 `DFS` 方法，它会调用 `DFSUtil` 方法，从指定的节点开始进行深度优先搜索。最后，在 `main` 方法中，我们创建了一个包含 4 个节点的图，向其中添加了 6 条边，并从节点 2 开始进行深度优先搜索，输出结果为 `2 0 1 3`。

#### 4、广度优先搜索算法 ####

广度优先搜索（BFS）是一种用于图形遍历的算法，它从图的某个顶点开始遍历，依次访问它的邻居节点，再访问邻居节点的邻居节点，以此类推，直到遍历完所有可达的节点。

BFS通常借助队列来实现，从源节点开始，先将该节点加入队列中，然后从队列中取出第一个节点，遍历它的所有邻居节点，并将这些邻居节点加入队列中，直到队列为空。

BFS的时间复杂度为O(V+E)，其中V为节点数，E为边数。

下面是使用Java实现的BFS代码示例：

import java.util.*;
    
    public class BFS {
        public static void bfs(int[][] graph, int start) {
            int n = graph.length; // 节点数
            boolean[] visited = new boolean[n]; // 标记是否已经访问
            Queue<Integer> queue = new LinkedList<>(); // 队列用于存放待访问的节点
            visited[start] = true; // 标记起点已经访问
            queue.offer(start); // 将起点加入队列中
    
            while (!queue.isEmpty()) {
                int node = queue.poll(); // 取出队列中的第一个节点
                System.out.print(node + " "); // 访问该节点
                for (int i = 0; i < n; i++) {
                    if (graph[node][i] == 1 && !visited[i]) {
                        // 如果该节点有邻居节点且邻居节点未被访问过，则将邻居节点加入队列中
                        visited[i] = true;
                        queue.offer(i);
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            int[][] graph = {
                    {0, 1, 1, 0, 0, 0},
                    {1, 0, 0, 1, 1, 0},
                    {1, 0, 0, 0, 1, 0},
                    {0, 1, 0, 0, 1, 1},
                    {0, 1, 1, 1, 0, 1},
                    {0, 0, 0, 1, 1, 0}
            };
            bfs(graph, 0); // 从节点0开始遍历
        }
    }

在上面的代码中，我们使用了一个boolean类型的数组visited来标记节点是否已经访问过，用一个队列来存放待访问的节点。在遍历每个节点的邻居节点时，我们使用邻接矩阵graph来表示图。如果该节点的邻居节点未被访问过，则将其加入队列中，同时将其标记为已访问。重复上述步骤，直到队列为空。

### 五、总结 ###

在排序算法方面，我们介绍了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序，并对它们的时间复杂度和应用场景进行了讲解。在查找算法方面，我们介绍了线性查找、二分查找、插值查找、斐波那契查找和哈希查找，并对它们的时间复杂度和应用场景进行了讲解。

在图的方面，我们介绍了图的基本概念和表示方法，包括邻接矩阵、邻接表和关联矩阵，并介绍了深度优先搜索和广度优先搜索两种常见的图搜索算法。我们还使用Java语言实现了各种算法的示例代码，方便读学习和理解。

总之，掌握数据结构和算法是计算机科学中非常重要的基础知识，本文旨在为读者提供一些基本概念和算法实现的思路和示例代码，希望对读者有所帮助。

[d8ccce366ce5fac4f2e56a3efce18034.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e0ba073810b54744b66ce82b6703cccc.png
[aa9170b3e459e3d80e609ffa4c747c55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/090bbd58de2546eba83c8c8afc0e0baa.png
[e142bc496167061d643027026800bc16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/5007addac7a941a9a9640b0d13bd1a2e.png
[5eb611243758deba42284bf1e28b738c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/56ab1c608738419fb21f15acb6ab66f0.png
[c2e16f01ed43b59d9ee3218ecf8fe895.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/791ccb758a5b453e9d830a87cf9a5685.png