java 数据结构和算法

### Java 数据结构与算法知识点详解 #### 一、数组与简单排序 ##### 数组 **概念**：数组是一种数据结构，用于存储具有相同类型的多个值。数组中的元素可以通过索引进行访问。 **特点**： - **类型统一**：数组中的所有元素必须具有相同的类型。 - **索引访问**：数组元素可以通过索引来访问，索引从0开始。 - **内存连续**：数组在内存中是连续存储的，这使得数组在某些操作上非常高效。 **一维数组** - **声明**：`type arrayName[];` - **初始化**： - **动态分配**：`type[] arrayName = new type[size];` - **静态初始化**：`type[] arrayName = {value1, value2, ...};` - **访问元素**：`arrayName[index];` **多维数组** - **声明**：`type arrayName[][];` - **初始化**：`type[][] arrayName = new type[size1][size2];` - **访问元素**：`arrayName[rowIndex][columnIndex];` **注意事项**： - Java会对数组下标进行越界检查，如果访问的索引超出了数组的有效范围，将会抛出`ArrayIndexOutOfBoundsException`异常。 - Java中的数组是动态分配的，这意味着在程序运行时可以动态地分配和调整数组大小。 ##### 简单排序 **冒泡排序** - **思想**：通过重复遍历数组，比较相邻元素并交换位置，使得较大的元素逐渐向数组尾部移动。 - **效率**：时间复杂度为O(n^2)，其中n是数组长度。 - **稳定性**：稳定排序，即相等的元素保持原有的顺序不变。 - **Java实现**： ```java public void bubbleSort() { int in, out; for (out = nElems - 1; out > 0; out--) { for (in = 0; in < out; in++) { if (a[in] > a[in + 1]) { swap(in, in + 1); } } } } ``` **选择排序** - **思想**：每次从未排序的部分找出最小（或最大）元素，放到已排序序列的末尾。 - **效率**：时间复杂度为O(n^2)。 - **稳定性**：不稳定排序，即相等的元素可能会改变原有顺序。 - **Java实现**： ```java public void selectSort() { int in, out, min; for (out = 0; out < nElems - 1; out++) { min = out; for (in = out + 1; in < nElems; in++) { if (a[in] < a[min]) { min = in; } } swap(out, min); } } ``` **插入排序** - **思想**：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录增1的有序表。 - **效率**：平均时间复杂度为O(n^2)，但在部分有序的情况下可以达到接近O(n)的效率。 - **稳定性**：稳定排序。 - **Java实现**： ```java public void insertionSort() { int in, out; for (out = 1; out < nElems; out++) { long temp = a[out]; in = out; while (in > 0 && a[in - 1] > temp) { a[in] = a[in - 1]; --in; } a[in] = temp; } } ``` ### 小结 本章节主要介绍了Java中的数组以及三种简单的排序算法——冒泡排序、选择排序和插入排序。数组作为基本的数据结构之一，在处理固定大小的数据集合时非常有用。而排序算法则是计算机科学中的基础内容，虽然这里介绍的几种排序算法效率相对较低，但对于理解和学习更复杂的排序算法具有重要的意义。接下来的内容将深入探讨其他数据结构和算法。