数据结构(2020.12更新)


  • 常见算法

  1. 插入排序

    i从0~len-1中，在前面的序列中给它重新安家（要不断挪其他元素）

  1. 冒泡排序

重复遍历要排序的数列，一次比较两个元素，如果顺序错误则交换。每次比较的数量从后往前-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class demo_sort {
    public static void main(String[] args) {
        //冒泡排序算法
        int[] numbers=new int[]{1,5,8,2,3,9,4};
        //需进行length-1次冒泡
        for(int i=0;i<numbers.length-1;i++)
        {
            for(int j=0;j<numbers.length-1-i;j++)
            {
                if(numbers[j]>numbers[j+1])
                {
                    int temp=numbers[j];
                    numbers[j]=numbers[j+1];
                    numbers[j+1]=temp;
                }
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for(i=0;i<numbers.length;i++)
            System.out.print(numbers[i]+" ");
    }
}

  1. 选择排序

    从一端到另一端，每次比较n,n-1….1个数据，每次挑个最小的，放入第1,2….n位。保证每次都能选出个最小的，放在开头。从头至尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。每次swap一个就Okay

  1. 希尔排序（分组插入排序）

    gap不断递减，在每次的分组里分别做排序。类推

  2. 归并排序（先分组再合并）

    不断分组，再比较，每在一对数组里选走一个数字，其分组指针向后移一位，继续进行比较。

  3. 快速排序

    拎出一个pivot(选个最左边的)，从hi开始，选第一个所指的，大于pivot则放在hi上，hi左移，读左移后指向的元素进行比较。相反同理，直至low和hi搞一块，则pivot赋值过去。

  4. 堆排序

    大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；


  • 红黑树（AVL平衡二叉树后裔）

  1. AVL树

找到插入路径上离插入节点最近的平衡因子的绝对值大于1的结点A，进行位置调整



  • ..


  • …