ARTS 第4周

发表于

ARTS （第4周）

开篇词

在这次看极客时间《数据结构与算法之美》专栏之前，我也曾使用过递归，但只是简单的单层的递归（简单的父子节点构成的数），关于递归，按照这篇专栏的介绍。

如何使用递归，应该有如下几个点：

1、中止条件，什么时候该结束递归。

2、递归如何进行拆分。

3、拆分后要做什么。

如果每次使用递归之前明确这几个点，其实会发现递归的使用很清晰明了。

出处：《数据结构与算法之美》（作者：王争）

https://time.geekbang.org/column/intro/126

本周：

递归、各类经典排序

Algorithm 算法

经典的排序算法

按照极客时间专栏里介绍的排序算法。

我写了5种，冒泡排序，插入排序，选择排序，归并排序，快速排序。

以下就是代码

冒泡排序

冒泡排序没什么好说的，双重循环，逐个比对，然后对调，是这几个算法里最简单也最容易理解的的排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
	 * 冒泡排序
	 * 
	 * @author lfy
	 */
	public void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				// 当i比j大的时候，2个数字位置对换
				if (arr[i] > arr[j]) {
					// 对换
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}

		}

	}
选择排序

选择排序，思路也比较容易理解，就是第一次循环查找最小的数字，放到数组的第一个位置，第二次继续在剩下的数据里找最小的，放到第二个位置，以次类推下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
	 * 选择排序
	 * 
	 * @author lfy
	 */
	public void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int min = i;// 最小坐标
			for (int j = i + 1; j < arr.length; j++) {
				// 遍历找出最小
				if (arr[min] > arr[j]) {
					min = j;
				}
			}
			// 将最小的和i进行对换
			int temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}
插入排序

插入排序，将数据分为已排序过的和未排序的2个区间。

刚开始的时候，将数组第一个数字当作已排序区间。

后续的数据，会逐个与已排序过的数据进行比对和对调，直到达到正确的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
	 * 插入排序
	 * 
	 * @author lfy
	 */
	public void insertionSort(int[] arr) {

		for (int i = 0; i < arr.length; i++) {
			int temp = arr[i];// 缓存
			int j = i - 1;// 和之前的数比较
			for (; j >= 0; j--) {
				// 若当前j坐标的数字更小,则往后挪一位
				if (arr[j] > temp) {
					arr[j + 1] = arr[j];
				} else {
					break;
				}

			}
			// 将缓存的数值插入到合适的位置
			arr[j + 1] = temp;
		}
	}
归并排序

归并排序的思想就是分而治之，将一段数据以中心的，分成2个区间，然后利用递归继续拆分，分到不能再分为止，然后将无法继续拆分的数据进行排序，排序完成后，因为是递归，所以会逐层向上，进行排序。

这个是我写的第一个排序方式，后来发现merge方法里的temp数组太大了。所以我再后面又改了一版

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
/**
	 * 归并排序
	 * 
	 * @author lfy
	 */
	public void mergeSort(int[] arr, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			int estart = mid + 1;

			// 以中点进行双路归并
			mergeSort(arr, start, mid);
			mergeSort(arr, estart, end);
			// 归并完成后 进行融合
			merge(arr, start, mid, end);
		}

	}

	/**
	 * 归并
	 * 
	 * @author lfy
	 * @time 2019年4月13日-下午4:13:38
	 * @param a
	 *            数据
	 * @param s
	 *            起始
	 * @param m
	 *            中间
	 * @param e
	 *            结束
	 */
	private void merge(int[] a, int s, int m, int e) {

		int[] temp = new int[a.length];
		for (int ix = s; ix <= e; ix++) {
			temp[ix] = a[ix];
		}
		int i = s;
		int p1 = s;// 前段数组指针
		int p2 = m + 1;// 后段数组指针
		while (p1 <= m && p2 <= e) {
			if (temp[p1] < temp[p2]) {
				a[i++] = temp[p1++];
			} else {
				a[i++] = temp[p2++];
			}
		}
		while (p1 <= m) {
			a[i++] = temp[p1++];
		}
		while (p2 <= e) {
			a[i++] = temp[p2++];
		}

	}

下面这个是改进过的

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
/**
	 * 归并排序
	 * 
	 * @author lfy
	 */
	public void mergeSort2(int[] arr, int s, int e) {
		if (e > s) {
			int m = (s + e) / 2;
			// 拆分成2个
			mergeSort2(arr, s, m);
			mergeSort2(arr, m + 1, e);
			merge2(arr, s, m, e);

		}

	}

	// 合并
	private void merge2(int[] a, int s, int m, int e) {
		int[] temp = new int[e - s + 1];
		// 备份
		for (int i = s, j = 0; i <= e; i++, j++) {
			temp[j] = a[i];
		}
		int p1 = 0;// 前半段指针
		int pe1 = temp.length / 2 - 1;// 前半段的最终坐标
		int p2 = pe1 + 1;// 后半段指针
		int pe2 = temp.length - 1;// 后半段的最终坐标
		while (p1 <= pe1 && p2 <= pe2) {
			if (temp[p1] < temp[p2])
				a[s++] = temp[p1++];
			else
				a[s++] = temp[p2++];
		}
		while (p1 <= pe1) {
			a[s++] = temp[p1++];
		}
		while (p2 <= pe2) {
			a[s++] = temp[p2++];
		}
	}
快速排序

快速排序是一个使用比较多的排序。也用到了递归进行拆分，不过拆分条件和归并排序不一样。是根据基准点进行拆分的，每次执行都会找一个基准点，然后把比基准点小的数据放到基准点前面，比基准点大的放到基准点后面。这样多次递归之后，就会得到一个有序的数组。

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
/**
	 * 快速排序
	 * 
	 * @author lfy
	 */
	public void quickSort(int[] arr, int s, int e) {
		if (e > s) {// 停止条件
			System.out.println(s+"-"+e);
			int p = qucik(arr, s, e);
			quickSort(arr, s, p-1);
			quickSort(arr, p+1, e);
		}
	}

	public int qucik(int[] arr, int s, int e){
		int pivot =arr[s];//基准点
		while(e>s){
			//从最右边开始 查找第一个小于基准点的数值
			while (e>s&&arr[e]>pivot) {
				e--;
			}
			//找到后，首次覆盖基准点，后续则覆盖下个循环里找到的点
			//如果未找到 则s==e
			arr[s]=arr[e];
			//从右边查找第一个大于基准点的数值
			while (e>s&&arr[s]<pivot) {
				s++;
			}
			//找到后，覆盖前一个循环里找到的点
			//如果未找到 则s==e
			arr[e]=arr[s];
		}
		arr[s]=pivot;
		return e;
	}

Review 英文文章

http://tomcat.apache.org/

tomcat的官网，大致介绍了tomcat和tomcat的使用

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的9-12篇

学习了递归的实际用法和几个经典的排序算法。

出处：《数据结构与算法之美》（作者：王争）

https://time.geekbang.org/column/intro/126

Share 分享

在这次看专栏之前，我也曾使用过递归，但只是简单的单层的递归（简单的父子节点构成的数），关于递归，按照这篇专栏的介绍。

如何使用递归，应该有如下几个点：

1、中止条件，什么时候该结束递归。

2、递归如何进行拆分。

3、拆分后要做什么。