Java常用数据结构和算法
2021-07-15 22:07
标签：int 没有 -o 结构 OLE 红黑树 break 查找 atom 二叉树： 1、每个结点不能多于两个子树； 2、一颗平衡二叉树的深度要比及结点个数N小得多。 二叉查找树： 1、结点x的所有左子树的值小于x，所有右子树的值大于x； AVL树： 1、一种带有平衡条件的二叉查找树； 2、每个结点的左子树和右子树深度最多差1。 红黑树： 1、树的颜色只能为红色或黑色的一种平衡二叉树； 2、树的根结点和叶子结点必须为黑色； 3、红色结点的子结点必须为黑色，且必存在； 4、任一结点到其每个叶子结点黑色的结点树相同； 5、从根到叶子的最长的可能路径不多于最短的可能路径的两倍长 红黑树与平衡二叉树： 红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。 平衡二叉树又被称为AVL树 红黑树有更好的效率，更高的统计性能 鸡尾酒排序： Java常用数据结构和算法 标签：int 没有 -o 结构 OLE 红黑树 break 查找 atom 原文地址：https://www.cnblogs.com/shuchen007/p/9535590.htmlprivate static void sort(int[] arrys) {
int tmp = 0;
for (int i = 0; i arrys.length/2; i++) {
boolean isSorted = true;
for (int j = i; j arrys.length-i-1; j++) {
if(arrys[j]>arrys[j+1]){
tmp = arrys[j];
arrys[j] = arrys[j+1];
arrys[j+1] = tmp;
isSorted = false;
}
}
if(isSorted){
break;
}
isSorted = true;
for (int j = arrys.length-i-1; j > i; j--) {
if(arrys[j]arrys[j-1]){
tmp = arrys[j];
arrys[j] = arrys[j-1];
arrys[j-1] = tmp;
isSorted = false;
}
}
if(isSorted){
break;
}
}
}
private static void sort(int[] arrys,int low, int high) {
int start = low;
int end = high;
int key = arrys[start];
while(end>start){
while(end>start&&arrys[end] >= key)//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if(key >= arrys[end]){
int tmp = arrys[end];
arrys[end] = arrys[start];
arrys[start] = tmp;
}
while(end>start&&key >= arrys[start])
start++;
if(arrys[start] >= key){
int tmp = arrys[end];
arrys[end] = arrys[start];
arrys[start] = tmp;
}
//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
if(start > low){
sort(arrys, low, start-1);//左边序列。第一个索引位置到关键值索引-1
}
if(high>end){
sort(arrys, end+1, high);//右边序列。从关键值索引+1到最后一个
}
}