Java中的集合算法：排序算法、查找算法、遍历算法
Java中的集合算法：排序算法、查找算法、遍历算法
1. 排序算法
排序算法是一种将数组或列表中的元素按照特定顺序排列的算法。Java中的集合框架提供了多种排序算法，例如冒泡排序、插入排序、选择排序、快速排序、归并排序等。
1.1 冒泡排序
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}冒泡排序是一种简单的排序算法，它通过重复地交换相邻的元素，将较小的元素逐渐交换到数组的前面。时间复杂度为O(n^2)。
1.2 插入排序
public static void insertSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}插入排序是一种简单的排序算法，它通过将一个元素插入到已经排序好的序列中，从而得到一个新的、更长的有序序列。时间复杂度为O(n^2)。
1.3 选择排序
public static void selectSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}选择排序是一种简单的排序算法，它通过从未排序的序列中选择最小的元素，将其放到已排序的序列的末尾。时间复杂度为O(n^2)。
1.4 快速排序
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int i = left;
int j = right;
int pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}快速排序是一种高效的排序算法，它通过选择一个基准值，将大于基准值的元素放在右边，小于基准值的元素放在左边，然后对左右两部分分别进行快速排序。时间复杂度为O(nlogn)。
1.5 归并排序
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
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++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}归并排序是一种稳定的排序算法，它通过将一个序列拆分成两个子序列，分别进行排序，然后将排序好的子序列合并成一个有序序列。时间复杂度为O(nlogn)。
2. 查找算法
查找算法是一种在数据结构中查找指定元素的算法。Java中的集合框架提供了多种查找算法，例如顺序查找、二分查找、哈希查找等。
2.1 顺序查找
public static int seqSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}顺序查找是一种简单的查找算法，它通过从头到尾顺序扫描一个序列，查找指定元素。时间复杂度为O(n)。
2.2 二分查找
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;
}二分查找是一种高效的查找算法，它通过将一个有序序列分成两半，判断指定元素在哪一半中，然后继续在该半序列中进行查找。时间复杂度为O(logn)。
2.3 哈希查找
public static int hashSearch(int[] arr, int target) {
int[] hashTable = new int[100];
for (int i = 0; i < arr.length; i++) {
int hash = arr[i] % 100;
while (hashTable[hash] != 0) {
hash = (hash + 1) % 100;
}
hashTable[hash] = arr[i];
}
int hash = target % 100;
while (hashTable[hash] != 0) {
if (hashTable[hash] == target) {
return hash;
}
hash = (hash + 1) % 100;
}
return -1;
}哈希查找是一种基于哈希表的查找算法，它通过将一个元素的关键字作为哈希表的索引来进行查找。时间复杂度为O(1)。
3. 遍历算法
遍历算法是一种按照某种顺序依次访问一个数据结构中的所有元素的算法。Java中的集合框架提供了多种遍历算法，例如迭代器遍历、for-each遍历、Lambda表达式遍历等。
3.1 迭代器遍历
List<Integer> list = new ArrayList<>();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
int i = iterator.next();
}迭代器遍历是一种基于迭代器的遍历算法，它通过迭代器依次访问一个集合中的所有元素。迭代器遍历可以在遍历过程中对集合进行增删操作，但是不能修改元素。
3.2 for-each遍历
List<Integer> list = new ArrayList<>();
for (int i : list) {
// do something
}for-each遍历是一种基于for-each语句的遍历算法，它通过for-each语句依次访问一个集合中的所有元素。for-each遍历不能在遍历过程中对集合进行增删操作，但是可以修改元素。
3.3 Lambda表达式遍历
List<Integer> list = new ArrayList<>();
list.forEach(i -> {
// do something
});Lambda表达式遍历是一种基于Lambda表达式的遍历算法，它通过Lambda表达式依次访问一个集合中的所有元素。Lambda表达式遍历可以在遍历过程中对集合进行增删修改操作。
本文为翻滚的胖子原创文章,转载无需和我联系,但请注明来自猿教程iskeys.com
- 最新评论
- 总共0条评论
