文章目录

   以前没学过算法课,所以这学期选算法的时候义无反顾的选了“算法二班”,基础班,即菜鸟班。上星期听了次课后感觉老师很不错,很有激情。一开始很多人选算法一班,估计是看选的人比较多吧。结果上完上午的课,下午的时候一大帮一班的人跑到了我们二班,据说一班的老师比较装,用的英文PPT,而且各种“这些你们懂的,我就不解释了”,2333。后来去教务处改被停掉的“网络安全”课时,发现好多人跑去调课,要从一班调到二班,照这样下去别一班因为人太少给砍掉啊,这样我们班一个教室坐那么多人估计得挤得够呛。

   因为算法基础较差,所以听从了老师的建议,准备从头开始,从易到难,把老师每节课讲到的所有的基本算法实现一遍,加深自己的理解。虽然说学数学出身,理解这些算法没啥问题,但是从理解到实现远远没有想的那么简单。就比如这简单的插入排序与归并排序,原理看起来是那么的简单,但是我却花费的足足一上午才实现,而且是在参考了ppt中给出的伪代码的情况下,当然给的c++代码没看。归并排序没有给伪代码,想了半天才照着ppt上的图解一点点的扣完。

   都是些基础的东西,大神就直接跳过吧,给自己留点印记,希望能给和我一样的菜鸟们一点帮助,该加注释的部分都加了注释。

   插入排序部分:

   给出了两种实现方式,原理都一样,只不过第一种更巧妙,第二种更直观。

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
/**
* 插入排序手动实现
* @author jrhu05
*
*/
public class InsertionSort {
public static void main(String[] args) {
int[] a={8,2,4,9,3,6};
insertSort2(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}

}
public static void insertSort(int[] a) {
int length=a.length;
for(int i=1;i<length;i++){
int key=a[i];
int j=i-1;
while (j>=0&&a[j]>=key) {
a[j+1]=a[j];
j--;
}
a[j+1]=key;//上一步j自减了1,所以要给a[j+1]赋值
}
}
public static void insertSort2(int[] a) {
int length=a.length;
int j,t;
for(int i=1;i<length;i++){
int key=a[i];
int max=i-1;
for (j = 0; j < max; j++) {
if(a[j]>=key){
break;
}
}
for(t=i;t>j;t--){
a[t]=a[t-1];
}
a[j]=key;
}
}
}

   合并排序部分:

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
/**
* 合并排序的手动实现
* @author jrhu05
*
*/
public class MergeSort {
public static void main(String[] args) {
int[] a={8,2,4,9,3,6};
mergeSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
}

private static int[] mergeSort(int[] array) {
//如果数组长度大于1,则需要继续分解数组
if (array.length>1) {
int leftLength=array.length/2;
int rightLength=array.length-leftLength;
//创建两个新的数组
int[] left=new int[leftLength];
int[] right=new int[rightLength];
//将原数组中的值分别赋值到2个子数组中
for (int i = 0; i < left.length; i++) {
left[i]=array[i];
}
for (int i = 0; i < right.length; i++) {
right[i]=array[leftLength+i];
}
//递归利用合并排序,排序子数组
left=mergeSort(left);
right=mergeSort(right);
//设置初始索引,就像ppt里的那两个箭头类似
int i=0;
int j=0;
for (int k = 0; k < array.length; k++) {
//如果左边数据索引达到边界则取右边的值(防止越界)
//此时左边的数据全部已经取完了,只能从右边取了
if (i==leftLength&&j<rightLength) {
array[k]=right[j];
j++;//取到哪边的值之后就向后移一位
}else if (i<leftLength&&j==rightLength) {
//右边同理
array[k]=left[i];
i++;
}else if (i<leftLength&&j<rightLength) {
//如果两边均为到达边界则取较小的值
if (left[i]>right[j]) {
array[k]=right[j];
j++;
}else {
array[k]=left[i];
i++;
}
}

}
}
return array;
}
}

   下次课要学习递归与分治,一点点来吧。日积月累,算法寻径。


如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录