常用的数据结构和算法_常用算法 和数据结构

一、数据结构

1、队列

一种先进先出的数据结构

2、栈

一种后进先出的数据结构

3、树

树的遍历算法：

先序遍历

中序遍历

后续遍历

层序遍历

4、图

图的遍历算法：

深度优先遍历算法

广度优先遍历算法

二、基础算法

1、排序算法

【1】快速排序算法

选择一个标杆，每一趟遍历比较下来确定标杆的位置使标杆左边的数比他小右边的数比他大

目标一趟下来确定标杆位置，使左边比他小右边比他大

假设将最后一位设为标杆

从左往右遍历，如果值小于等于标杆，遍历下一个，如果值比标杆大交换该值和标杆值；操作完后标杆左边的都比他小，但是右边可能也存在比他小的。

因此从右往前遍历，如果值比标杆大继续从右往前遍历，如果值比标杆小，则交换标杆和该值，接着又从左往右遍历。知道遍历的下标和标杆的下标重合，则该趟比较完成。

伪代码

flag_idx =  length
// 从左往右遍历
for (i =0 to end) {
	if (a[i] > a[flag_idx]) {
		//交换
		swap(a[i], a[flag_idx]);
		flag_idx = i;
		for(j = end to 0) {
			if (a[j] < a[flag_idx]) {
				swap(a[i], a[flag_idx]);
				flag_idx = j;
				break;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

具体实现代码: 先不管从左往右和从右往左每次从什么位置开始

    public static void sortAndGetIdx(int[] a, int start, int end) {
        int flg = end - 1;
        int temp = a[end - 1];
        // 从左往右
        for (int i =start; i<end-1 ; i++) {
            // 当前值比标杆大，且下标比标杆小时交换
            if (temp < a[i] && i < flg) {
                int k = a[i];
                a[i] = a[flg];
                a[flg] = k;
                // 标杆交换到 i 位置
                flg = i;
                // 从右往左遍历
                for (int j = end -1 ; j>=start; j--) {
                    if (temp > a[j] && j >flg) {
                        int l = a[j];
                        a[j] = a[flg];
                        a[flg] = l;
                        // 标杆交换到j位置
                        flg = j;
                        // 继续从左往右遍历
                        break;
                    }
                }
            }
        }

//        System.out.println(flg);
        if (start < flg - 1) {
            sortAndGetIdx(a, start, flg -1);
        }
        if (end > flg + 1) {
            sortAndGetIdx(a, flg + 1, end);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

优化后

    public static void sortAndGetIdx(int[] a, int start, int end) {
        int flg = end - 1;
        int temp = a[end - 1];
        
        // 从左往右，只需要遍历到flg位置，因为flg右边的都比它大了
        for (int i = start; i < flg; i++) {
            
            // 当前值比标杆大，且下标比标杆小时交换
            if (temp < a[i] && i < flg) {
                int k = a[i];
                a[i] = a[flg];
                a[flg] = k;
                // 标杆交换到 i 位置
                flg = i;
                
                // 从右往左遍历； 只需要遍历到flg位置即可；因为flg左边的都比他小了
                for (int j = end - 1; j > flg; j--) {
                    if (temp > a[j] && j > flg) {
                        int l = a[j];
                        a[j] = a[flg];
                        a[flg] = l;
                        // 标杆交换到j位置
                        flg = j;
                        // 继续从左往右遍历
                        break;
                    }
                }
            }
        }

//        System.out.println(flg);
        if (start < flg - 1) {
            sortAndGetIdx(a, start, flg - 1);
        }
        if (end > flg + 1) {
            sortAndGetIdx(a, flg + 1, end);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

【2】冒泡排序算法

每一趟排序下来大的沉底

一趟比较的过程：

从左往右遍历，如果后一个数比前一个大，则继续遍历，如果后一个数比前一个数小则交换交换，拿后一个数继续跟后面的数比较，知道遍历到最后将大的数沉底。

一趟排序的伪代码：

for(i from 1 to end) {
	if (a[i] < a[i-1]) {
		swap(a[i], a[i-1])
	}
}
1
2
3
4
5

代码：

public class BubblingSort {

    public static void main(String args[]) {
        int a[] = new int[]{3,6,9,4,6,7};

        for (int i=0;i<a.length;i++) {
            // 一趟排序大的沉底
            for (int j = 1; j< a.length-i; j++) {
                if (a[j] < a[j - 1]) {
                    int k = a[j];
                    a[j] = a[j-1];
                    a[j - 1] = k;
                }
            }
        }

        for(int i=0;i<a.length; i++) {
            System.out.println(a[i]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

【3】交换排序

从左往右遍历，如果后面的数比当前的数小则交换

public class ChangeSort {

    public static void main(String[] args) {
        int a[] = new int[]{3, 6, 9, 4, 6, 7};

        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[i]) {
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                }
            }
        }

        // 输出结果
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

【4】选择排序

每一趟下来挑一个最大的放在末尾的位置，中间先不交换。

public class SelectSort {
    public static void main(String[] args) {
        int a[] = new int[]{3, 6, 9, 4, 6, 7};

        for (int i = a.length - 1; i >= 0; i--) {
            int max = a[i];
            int idx = i;

            // 从剩下的数中选出一个最大的数
            for (int j = i - 1; j >= 0; j--) {
                if (a[j] > max) {
                    max = a[j];
                    idx = j;
                }
            }

            // 将最大的数放末尾；交换
            if (idx != i) {
                int k = a[idx];
                a[idx] = a[i];
                a[i] = k;
            }
        }

		// 输出打印结果
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

【5】插入排序

从左往右遍历，如果发现值位置不对，则把它插入到前面排序好的数组中正确的位置中

举例：

4567317； 遍历到3时3挪动到4前面，4后面到3之前的所有数都往后后移一位

public class InsertSort {
    public static void main(String[] args) {
        int a[] = new int[]{3, 6, 9, 4, 6, 7};

        for (int i = 1; i < a.length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果i这个数位置不对，把它放到i-j中间的正确位置上去
                if (a[j] > a[i]) {
                    int temp = a[i];
                    // 将j开始后面到i之前的数往后挪一位
                    move(a, j, i-1);
                    a[j] = temp;
                }
            }
        }

        // 输出结果
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    /**
     * 功能描述: 将数组a中下标为start到end位置的数往后挪一位
     *
     * @param a
     * @param start
     * @param end
     * @return void
     * @see [相关类/方法](可选)
     * @since [产品/模块版本](可选)
     */
    public static void move(int[] a, int start, int end) {
        for (int i = end; i >= start; i--) {
            a[i + 1] = a[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

【6】归并排序

一般只两路归并排序，核心思想是将两个有序集合合并成一个有序的集合；分割–>合并

做法是采用一个临时的数组来存在排序后的临时结果，遍历两个集合，首先比较两个集合第一个元素大小，将小的放到临时集合的第一个位置，然后将小的所在的集合的下一个元素和另一个集合的元素比较。

两个有序集合合并成一个有序集合的伪代码

mergeSort(a[], b[]) {
	temp[]
	for (int i from 0 to a.leng) {
		int jTag = 0;
		for (int j from jTag to b.leng) {
			if (b[j] > a[i]) {
				put a[i] to temp;
				break;
			} else {
				put b[j] to temp;
				jTag = j+1; // 下次从j的位置比较
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

一个集合按mid分成两部分有序的集合，合并成一个有序的集合

mergSort(a[], mid) {
	temp[]
	for (int i from 0 to mid) {
		int jTag = mid+1;
		for (int j from jTag to a.len) {
			if (a[j] > a[i]) {
				put a[i] to temp;
				break;
			} else {
				put a[j] to temp;
				jTag = j+1; // 下次从j的位置比较
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并的代码

    public static void merge(int[] a, int start, int mid, int end, int[] temp) {
        int k = 0;
        int iTag = start;
        int jTag = mid + 1;
        // 遍历左边的有序数组
        for (int i = start; i <= mid; i++) {
            // 遍历右边的有序数组
            for (int j = jTag; j <= end; j++) {
                // 如果右边比左边数大
                if (a[j] > a[i]) {
                    // 将左边的数放到临时数组中
                    temp[k] = a[i];
                    // 左边数组复制的位置
                    iTag = i + 1;
                    k++;
                    // 左边数组的索引+1，然后继续和右边的该值比较
                    break;
                } else {
                    // 右边的数比左边的小，右边的数放到临时数组中
                    temp[k] = a[j];
                    // 下次遍历j的时候从jtag的位置遍历
                    jTag = j + 1;
                    k++;
                }

            }
        }

        // 将左边剩余的大数复制到temp数组中
        for (int i = iTag; i <= mid; i++) {
            temp[k] = a[i];
            k++;
        }

        // 将右边剩余的大数复制到temp数组中
        for (int j = jTag; j <= end; j++) {
            temp[k] = a[j];
            k++;
        }

        // 把temp重写到a中
        for (int i = start; i <= end; i++) {
            a[i] = temp[i - start];
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

排序算法

public class MergeSort {
    public static void main(String[] args) {
        int a[] = new int[]{6, 4, 3, 2, 7, 9 , 8};
        sort(a, 0, a.length-1, new int[a.length]);
        // 输出结果
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public static void sort(int[] a, int start, int end, int[] temp) {
        int mid = (start + end) / 2;
        // 如果数组长度<2则无需再分割直接合并
        if (end - start < 2) {
            merge(a, start, mid, end, temp);
            return;
        }
        // 分割
        sort(a, start, mid, temp);
        sort(a, mid + 1, end, temp);
        merge(a, start, mid, end, temp);
    }

    public static void merge(int[] a, int start, int mid, int end, int[] temp) {
        int k = 0;
        int iTag = start;
        int jTag = mid + 1;
        // 遍历左边的有序数组
        for (int i = start; i <= mid; i++) {
            // 遍历右边的有序数组
            for (int j = jTag; j <= end; j++) {
                // 如果右边比左边数大
                if (a[j] > a[i]) {
                    // 将左边的数放到临时数组中
                    temp[k] = a[i];
                    // 左边数组复制的位置
                    iTag = i + 1;
                    k++;
                    // 左边数组的索引+1，然后继续和右边的该值比较
                    break;
                } else {
                    // 右边的数比左边的小，右边的数放到临时数组中
                    temp[k] = a[j];
                    // 下次遍历j的时候从jtag的位置遍历
                    jTag = j + 1;
                    k++;
                }

            }
        }

        // 将左边剩余的大数复制到temp数组中
        for (int i = iTag; i <= mid; i++) {
            temp[k] = a[i];
            k++;
        }

        // 将右边剩余的大数复制到temp数组中
        for (int j = jTag; j <= end; j++) {
            temp[k] = a[j];
            k++;
        }

        // 把temp重写到a中
        for (int i = start; i <= end; i++) {
            a[i] = temp[i - start];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

【7】 堆排序

步骤：

1、原地初始建堆，通过shiftdow建堆

2、重复执行下面操作，直到堆的大小为1

【1】交换堆顶元素和尾元素

【2】堆的元素数量减1

【3】对0位置进行一次shiftdown

【8】希尔排序

希尔排序听名字就能想到是Shell提出来的，只是对直接插入排序做了一个基本的改进。什么改进呢？

希尔排序是把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序。

步长数组：｛4，2，1｝

算法步骤

• 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        shellSort(arr);

        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }

    private static void shellSort(int[] arr) {
        //step:步长
        for (int step = arr.length / 2; step > 0; step /= 2) {
            //对一个步长区间进行比较 [step,arr.length)
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;

                //对步长区间中具体的元素进行比较
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    //j为左区间的取值，j+step为右区间与左区间的对应值。
                    arr[j + step] = arr[j]; 
                }
                //此时step为一个负数，[j + step]为左区间上的初始交换值
                arr[j + step] = value;  
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

【9】外部排序

其实就是归并排序的应用

2个2G的有序文件如何变成1个有序的4G文件呢？

先从第一个有序的文件中读取1G，从另一个有序的文件中读取1G；

比较这2G，如果一个文件的1G先排序完则把该文件的另1G加载到内存。

2、字符串匹配

给两个字符串A和B，找出在字符串A中B的起始位置

思路：

先算下B的长度len，从第一个字符开始遍历截取长度为len个数的字符得到串C，判断串C和串B是否相等，相等则说明该字符的位置为起始位置。

public class StringMatch {

    public static void main(String[] args) {
        System.out.println(getIdx("abcdefgh", "cde"));
    }

    public static int getIdx(String a, String b) {
        int len = b.length();
        String c;
        for (int i = 0; i < a.length(); i++) {
            if (a.length() - i < len) {
                break;
            }
            c = a.substring(i, i + len);
            if (b.equals(c)) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、TopK问题

从n个数中找出前K个最大的数？

思路一：遍历K此，每次挑一个最大的数

思路二：从前往后遍历，每次替换最小的那个数

public class TopK {

    public static void main(String[] args) {
        int[] a = new int[]{1,2,9999,11,7,89,22};
        int[] b = getTopK(a, 3);

        for (int i = 0; i < b.length; i++) {
            System.out.println(b[i]);
        }
    }

    public static int[] getTopK(int[] a, int k) {
        int[] topK = new int[k];
        for (int i = 0; i < a.length; i++) {
            if (i < k) {
                topK[i] = a[i];
            } else {
                int dis = 0;
                // 最小数的下标
                int idx = 0;
                for(int j=0; j<k; j++) {
                    if (a[i] - topK[j] > dis) {
                        dis = (a[i] - topK[j]);
                        idx = j;
                    }
                }
                if (dis > 0) {
                    topK[idx] = a[i];
                }
            }
        }
        return topK;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

4、雪花算法

雪花算法是一种生成唯一序列号的算法，能够生成一连串顺序的序列号，不同于UUID是无序的

SnowFlake算法生成id的结果是一个64bit大小的整数，它的结构如下图：

1bit，不用，因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0。

41bit-时间戳，用来记录时间戳，毫秒级。
- 41位可以表示2^41-1个数字，
- 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 2^41-1，减1是因为可表示的数值范围是从0开始算的，而不是1。
- 也就是说41位可以表示2^41-1个毫秒的值，转化成单位年则是
$$(2^{4}1-1)/(1000\ast 60\ast 60\ast 24\ast 365)=69年$$
10bit-工作机器id，用来记录工作机器id。
- 可以部署在1024个节点，包括5位datacenterId和5位workerId
- 5位（bit）可以表示的最大正整数是2^5-1，即可以用0、1、2、3、…31这32个数字，来表示不同的datecenterId或workerId

12bit-序列号，序列号，用来记录同毫秒内产生的不同id。
- 12位（bit）可以表示的最大正整数是2^12-1，即可以用0、1、2、3、…4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号。

由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。

SnowFlake可以保证：

1. 所有生成的id按时间趋势递增
2. 整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）

public class IdWorker{

    //下面两个每个5位，加起来就是10位的工作机器id
    private long workerId;    //工作id
    private long datacenterId;   //数据id
    //12位的序列号
    private long sequence;

    public IdWorker(long workerId, long datacenterId, long sequence){
        // sanity check for workerId
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
        }
        System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    //初始时间戳
    private long twepoch = 1288834974657L;

    //长度为5位
    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;
    //最大值
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    //序列号id长度
    private long sequenceBits = 12L;
    //序列号最大值
    private long sequenceMask = -1L ^ (-1L << sequenceBits);
    
    //工作id需要左移的位数，12位
    private long workerIdShift = sequenceBits;
   //数据id需要左移位数 12+5=17位
    private long datacenterIdShift = sequenceBits + workerIdBits;
    //时间戳需要左移位数 12+5+5=22位
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    
    //上次时间戳，初始值为负数
    private long lastTimestamp = -1L;

    public long getWorkerId(){
        return workerId;
    }

    public long getDatacenterId(){
        return datacenterId;
    }

    public long getTimestamp(){
        return System.currentTimeMillis();
    }

     //下一个ID生成算法
    public synchronized long nextId() {
        long timestamp = timeGen();

        //获取当前时间戳如果小于上次时间戳，则表示时间戳获取出现异常
        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    lastTimestamp - timestamp));
        }

        //获取当前时间戳如果等于上次时间戳（同一毫秒内），则在序列号加一；否则序列号赋值为0，从0开始。
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }
        
        //将上次时间戳值刷新
        lastTimestamp = timestamp;

        /**
          * 返回结果：
          * (timestamp - twepoch) << timestampLeftShift) 表示将时间戳减去初始时间戳，再左移相应位数
          * (datacenterId << datacenterIdShift) 表示将数据id左移相应位数
          * (workerId << workerIdShift) 表示将工作id左移相应位数
          * | 是按位或运算符，例如：x | y，只有当x，y都为0的时候结果才为0，其它情况结果都为1。
          * 因为个部分只有相应位上的值有意义，其它位上都是0，所以将各部分的值进行 | 运算就能得到最终拼接好的id
        */
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    //获取时间戳，并与上次时间戳比较
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    //获取系统时间戳
    private long timeGen(){
        return System.currentTimeMillis();
    }

    //---------------测试---------------
    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1,1,1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121