Java常用数据结构和算法

二叉树：

1、每个结点不能多于两个子树；

2、一颗平衡二叉树的深度要比及结点个数N小得多。

二叉查找树：

1、结点x的所有左子树的值小于x，所有右子树的值大于x；

AVL树：

1、一种带有平衡条件的二叉查找树；

2、每个结点的左子树和右子树深度最多差1。

红黑树：

1、树的颜色只能为红色或黑色的一种平衡二叉树；

2、树的根结点和叶子结点必须为黑色；

3、红色结点的子结点必须为黑色，且必存在；

4、任一结点到其每个叶子结点黑色的结点树相同；

5、从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

红黑树与平衡二叉树：

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。

平衡二叉树又被称为AVL树

红黑树有更好的效率，更高的统计性能

鸡尾酒排序：

<wiz_code_mirror>

private 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;

快速排序：

<wiz_code_mirror>

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到最后一个

巴特西