作者 | 张振华.Jack
责编 | 郭芮
出品 | CSDN 博客
Java数据结构
数据结构:
Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。
线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。
使用场景也非常多,如线程池、MQ、连接池等。
KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。
非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash)。
树形结构,作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成,可以有多个子节点。树,显然是由递归算法组成。
红黑树的5条性质:
树总结: 树在Java里面应用的也比较多。非排序树,主要用来做数据储存和展示。而排序树,主要用来做算法和运算,HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。
一致性Hash:
空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。 时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。 稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。
public static void main(String[] args) {
int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
System.out.println(binSearch(srcArray, 28));
}
/**
* 二分查找普通循环实现
*
* @param srcArray 有序数组
* @param key 查找元素
* @return
*/
public static int binSearch(int srcArray[], int key) {
int mid = srcArray.length / 2;
// System.out.println("=:"+mid);
if (key == srcArray[mid]) {
return mid;
}
//二分核心逻辑
int start = 0;
int end = srcArray.length - 1;
while (start <= end) {
// System.out.println(start+"="+end);
mid = (end - start) / 2 + start;
if (key < srcArray[mid]) {
end = mid - 1;
} else if (key > srcArray[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。
public static void main(String[] args) {
int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
System.out.println(binSearch(srcArray, 0,15,28));
}
/**
* 二分查找递归实现
*
* @param srcArray 有序数组
* @param start 数组低地址下标
* @param end 数组高地址下标
* @param key 查找元素
* @return 查找元素不存在返回-1
*/
public static int binSearch(int srcArray[], int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (srcArray[mid] == key) {
return mid;
}
if (start >= end) {
return -1;
} else if (key > srcArray[mid]) {
return binSearch(srcArray, mid + 1, end, key);
} else if (key < srcArray[mid]) {
return binSearch(srcArray, start, mid - 1, key);
}
return -1;
}
递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
---|---|---|---|
O(n²) | O(n) | O(n²) | O(1) |
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).
/**
* 冒泡排序
*
* ①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
* ②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
* ③. 针对所有的元素重复以上的步骤,除了最后一个。
* ④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
* @param arr 待排序数组
*/
public static void bubbleSort(int[] arr){
for (int i = arr.length; i > 0; i--) { //外层循环移动游标
for(int j = 0; j < i && (j+1) < i; j++){ //内层循环遍历游标及之后(或之前)的元素
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
System.out.println("Sorting: " + Arrays.toString(arr));
}
}
}
}
/**
* 快速排序(递归)
*
* ①. 从数列中挑出一个元素,称为"基准"(pivot)。
* ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
* ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
* @param arr 待排序数组
* @param low 左边界
* @param high 右边界
*/
public static void quickSort(int[] arr, int low, int high){
if(arr.length <= 0) return;
if(low >= high) return;
int left = low;
int right = high;
int temp = arr[left]; //挖坑1:
保存基准的值
while (left < right){
while(left < right && arr[right] >= temp){ //坑2:
从后向前找到比基准小的元素,插入到基准位置坑1中
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= temp){ //坑3:
从前往后找到比基准大的元素,放到刚才挖的坑2中
left++;
}
arr[right] = arr[left];
}
arr[left] = temp; //基准值填补到坑3中,准备分治递归快排
System.out.println("Sorting: " + Arrays.toString(arr));
quickSort(arr, low, left-1);
quickSort(arr, left+1, high);
}
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
---|---|---|---|
O(nlog₂n) | O(nlog₂n) | O(n²) | O(1)(原地分区递归版) |
热 文 推 荐
☞区块链+“中国制造”:一文看懂区块链如何提升供应链金融活力与效能!
点击阅读原文,参加中国开发者现状调查!