此博客文章的一系列博客文章第1部分有关数据结构。在此博客文章中，我们将介绍以下数据结构：
- 什么是数组？
- 如何声明数组？
(With JavaScript and Java) - 阵列的优势和缺点
- 优点
- 缺点
- 数组操作的时间复杂性
- 阵列操作的基本过程
(With JavaScript and Java)- 添加
- 删除
- 排序阵列
(With JavaScript and Java)- 合并排序
- 快速排序
- 搜索阵列
(With JavaScript and Java)- 二进制搜索
大批
什么是数组？
数组是存储在连续内存位置的项目的集合。这个想法是将同一类型的多个项目一起存储在一起。这使得通过简单地将偏移添加到基本值
来更容易计算每个元素的位置。为简单起见，我们可以想到一个楼梯的楼梯，每个步骤都会放置一个价值（如果说您的一个朋友）。在这里，您可以简单地了解他们所在的步骤来确定任何朋友的位置。
数组的索引从0到（数组的大小1）。例如，在下面给出的数组中，第一个元素2 is 0的索引。最后一个元素9 is 4的索引。
let arr = [2, 3, 4, 5, 9];
int[] arr = {2, 3, 4, 5, 9};
如何声明数组？
在JavaScript中，我们可以通过以下方式声明一个数组：
// Method 1
let arr = new Array();
// Method 2
let arr = [];
// Method 3
let arr = [1, 2, 3, 4, 5];
在Java中，我们可以通过以下方式声明一个数组：
// Method 1
int[] arr = new int[5];
// Method 2
int[] arr = {1, 2, 3, 4, 5};
阵列的优点和缺点
优点
- 数组易于实现。
- 阵列提供更好的缓存局部性，可以在性能上产生很大的影响。
- 数组提供O（1）搜索，如果我们知道索引。
缺点
- 阵列的大小是固定的：因此，我们必须提前知道元素数量的上限。同样，通常，分配的内存等于上限，而不论使用情况如何。
- 在各种元素中插入新元素是昂贵的，因为必须为新元素创建房间，并且要创建空间，并且现有元素必须转移。
- 在一系列元素中删除元素很昂贵，因为必须为新元素创建房间，并且要创建空间，并且现有元素必须转移。
- 在数组中搜索很昂贵，因为我们必须浏览所有元素才能找到我们要寻找的元素。
阵列操作的时间复杂性
| 操作 | 时间复杂性 |
|---|---|
| 访问 | o（1） |
| 搜索 | o（n） |
| 插入 | o（n） |
| 附加 | o（1） |
| 删除 | o（n） |
数组操作的基本过程
添加
- 最后添加一个元素：o（1）
- 在开始时添加一个元素：o（n）
- 中间添加一个元素：o（n）
// Add an element at the end
let arr = [1, 2, 3, 4, 5];
arr.push(6);
// Add an element at the beginning
let arr = [1, 2, 3, 4, 5];
arr.unshift(0);
// Add an element in the middle
let arr = [1, 2, 3, 4, 5];
arr.splice(2, 0, 2.5);
// Add an element at the end
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
newArr[arr.length] = 6;
// Add an element at the beginning
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length + 1];
newArr[0] = 0;
for (int i = 0; i < arr.length; i++) {
newArr[i + 1] = arr[i];
}
// Add an element in the middle
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length + 1];
for (int i = 0; i < 2; i++) {
newArr[i] = arr[i];
}
newArr[2] = 2.5;
for (int i = 2; i < arr.length; i++) {
newArr[i + 1] = arr[i];
}
消除
- 末尾删除元素：o（1）
- 开头删除元素：o（n）
- 中间删除一个元素：o（n）
// Remove an element at the end
let arr = [1, 2, 3, 4, 5];
arr.pop();
// Remove an element at the beginning
let arr = [1, 2, 3, 4, 5];
arr.shift();
// Remove an element in the middle
let arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);
// Remove an element at the end
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = arr[i];
}
// Remove an element at the beginning
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = arr[i + 1];
}
// Remove an element in the middle
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < 2; i++) {
newArr[i] = arr[i];
}
for (int i = 2; i < newArr.length; i++) {
newArr[i] = arr[i + 1];
}
遍历
- 遍历数组：o（n）
let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
int[] arr = {1, 2, 3, 4, 5};
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
排序数组
合并排序
- 时间复杂性：O（n log n）
- 空间复杂性：o（n）
- 合并排序是由约翰·冯·诺伊曼（John von Neumann）在1945年发明的鸿沟和征服算法。
- 合并排序是一种基于分隔和征服技术的分类技术。
- 最差的时间复杂性是α（n log n），它是最受人尊敬的算法之一。
合并排序算法如何工作？
将未分类的列表分为n个sublist，每个列表包含1个元素（1个元素列表被认为排序）。反复合并冠军制作新的分类订书机，直到只剩下1个冠军。这将是排序列表。
图像来源：wikimedia
合并排序算法实现
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
let arr = [5, 4, 3, 2, 1];
console.log(mergeSort(arr));
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
mergeSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void mergeSort(int[] arr, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
public static void merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (arr[i] < arr[j]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= mid) {
temp[k] = arr[i];
i++;
k++;
}
while (j <= end) {
temp[k] = arr[j];
j++;
k++;
}
for (int l = start; l <= end; l++) {
arr[l] = temp[l - start];
}
}
}
快速排序
- 时间复杂性：O（n log n）
- 空间复杂性：O（log n）
- 快速排序是一种高效的排序算法，基于将数据数组分配到较小的数组中。
快速排序算法如何工作？
快速排序可以这样工作：
- 从数组中选择一个称为枢轴的元素。
- 重新排序数组，以便所有具有小于枢轴的元素出现在枢轴之前，而所有具有大于枢轴的元素是在其之后的（无论哪种方式都可以使用）。分区后，枢轴处于最终位置。这称为分区操作。
- 递归将上述步骤应用于具有较小值的元素的子阵列，并分别应用于具有更大值的元素的子阵列。
图像来源：tutorialspoint
快速排序算法实现
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivot = arr[0];
let left = [];
let right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
let arr = [5, 4, 3, 2, 1];
console.log(quickSort(arr));
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int pivot = partition(arr, start, end);
quickSort(arr, start, pivot - 1);
quickSort(arr, pivot + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;
return i + 1;
}
}
搜索数组
搜索是在值列表中找到特定值的过程。搜索通常会回答对该值是否存在的真实还是错误。有时可能会修改以返回值的位置。
二进制搜索
- 时间复杂性：O（log n）
- 空间复杂性：O（1）
- 二进制搜索是一种快速搜索算法，其运行时复杂性为α（log n）。该搜索算法在鸿沟和征服的原则上起作用。为了使该算法正常工作，数据收集应以排序形式。
二进制搜索算法如何工作？
二进制搜索的工作原理：
- 二进制搜索首先将数组的中间元素与目标值进行比较。
- 如果目标值与中间元素匹配，则返回数组中的位置。
- 如果目标值小于或大于中间元素，则搜索分别在数组的下半部分继续，从而消除了另一半。
二进制搜索算法实现
function binarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
let arr = [1, 2, 3, 4, 5];
console.log(binarySearch(arr, 3));
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println(binarySearch(arr, 3));
}
public static int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
}
参考
谢谢阅读 ：）
在GitHub上关注我。