2017年11月26日，这样的日子不好受。

整日这样与电脑交朋友，都快忘记了生活，整天都无意学习。

2017年11月26日22:42:36

今由于看到以下内容中的数据结构，花了一天的时时间去看数据结构。

学java这么久来，都还没了解过数据结构，然后在网上看到一篇博客，让我燃起了学数据结构的斗志。

http://blog.csdn.net/iaiti/article/details/39268173

他里面引用了一句知乎的话，我这里也引用一下。

如果说 Java 是自动档轿车，C 就是手动档吉普。数据结构呢？是变速箱的工作原理。你完全可以不知道变速箱怎样工作，就把自动档的车子从 A 开到 B，而且未必就比懂得的人慢。写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。如果你对这两件事都不感兴趣也就罢了，数据结构懂得用就好。但若你此生在编程领域还有点更高的追求，数据结构是绕不开的课题。

Java 替你做了太多事情，那么多动不动还支持范型的容器类，加上垃圾收集，会让你觉得编程很容易。但你有没有想过，那些容器类是怎么来的，以及它存在的意义是什么？最粗浅的，比如 ArrayList 这个类，你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组，这种东西 C 是没有的，要自己实现。但是，具体怎么实现呢？如果你对这种问题感兴趣，那数据结构是一定要看的。甚至，面向对象编程范式本身，就是个数据结构问题：怎么才能把数据和操作数据的方法封装到一起，来造出 class / prototype 这种东西？

此外，很重要的一点是，数据结构也是通向各种实用算法的基石，所以学习数据结构都是提升内力的事情。

内存分配

1) 寄存器 。 最快的存储区，处理器内部，根据需求分配，不能自己控制，但是C/C++可以用register。

2)栈：位于RAM中，速度仅次于寄存器。存放的是基本变量和引用，在栈中的数据可以共享，在栈中的数据大小和生存周期必须确定。
栈存的一个是基本的数据类型，int i = 1; 其实i是一个指向int类型的引用。1存在栈中，i指向1的地址（作用和指针一个样），如果此时有int j = 1; 由于共享性，就不会再开辟
一个新的1的地址。直接让i和j指向同一个地址。
栈也存储对象的引用。

3)堆。存放所有的java对象。

4)常量存储。常量（注意常量和变量，int i =1是变量）,字符串，静态区的东西存储在此。

5)非RAM存储。

空间计算：

之前看到过空间和时间的关系，但是没理解，今天再次看到，仔细去研究了下，明白了一个究竟。还是某个博客讲排序时同时讲的时间问题才明白了。

大O表示法

设N为数据总数，加入插入一个数据时间为K。

那么线性查找总时间T=K*N/2，因为查找的话大概为比较数目的一半。

二分查找的话T=k*log2(N)。

大O表示法，O可以看成是order of，大约是的意思，k/2也是常数，所以可以看成是O(N)。

数组

Java中有两种数据类型，基本类型和对象类型，java中把数组当成对象，创建数组需要用new操作符。

在引用数组时，会在栈中开辟空间，空间存储着保存数据的地址，new操作符在堆中开辟了所需的空间，然后数组指向头地址。

，

然后分析看到了别人写得数组封装

好奇起研究了下，看完就了解了arrayList了

下面是封装代码：

1. public class UseArray {
2.     private int[] array;
3.     private int number = 0;
4.     public UseArray(int max){
5.         array = new int[max];
6.     }
7.     public void insert(int value){
8.         array[number] = value;
9.         number++;
10.     }
11.     public int find(int value){
12.         for (int i= 0; i < number; i++) {
13.             if(array[i]==value)
14.                 return i;
15.         }
16.         return number;
17.     }
19.     public boolean delete(int value){
20.         int index = find(value);
21.         if(index != number){
22.             for (int i = index; i < number-1; i++) {
23.                 array[i] = array[i+1];
24.             }
25.             number--;
26.             return true;
27.         }
28.         return false;
29.     }
31.     public void display(){
32.         for (int i = 0; i < number; i++) {
33.             System.out.printf(array[i]+" ");
34.         }
35.     }
36.     public static void main(String[] args) {
37.         UseArray ua  = new UseArray(5);
38.         ua.insert(1);
39.         ua.insert(2);
40.         ua.insert(6);
41.         ua.insert(7);
42.         ua.insert(3);
44.         ua.display();
45.         if(ua.find(5) != ua.number){
46.             System.out.println("find,the number index is "+ua.find(5));
47.         }else{
48.             System.out.println("not found!");
49.         }
50.         if(ua.delete(5)!=true){
51.             System.out.println("can not delete!");
52.         }
53.         ua.display();
54.     }
55. }

排序

冒泡排序

最后看了排序，以前觉得排序简单，然而自己写的时候还是有点棘手。要是在我不了解排序的情况下写个排序可能也就像冒泡排序一样吧，以前C语言考试就瞎写了一个排序，最后才知道那是冒泡。

下面是我复习的冒泡排序java代码：

运行结果：

冒泡排序就是大的数像后放，在排序的时候给一个中间变量，让大的数和小的数做交换。

选择排序：

首先默认一个最小值，然后再循环一次去找到比默认还小的最小值。如果找到了，就存入此值得下标，继续向数组后面查找。这次循环结束后，把小的值和前面的值进行交换。后面的循环依旧如此。

运行结果：

插入排序

这个排序相对于前面两个排序花了点时间去了解，还去http://zh.visualgo.net/可视化数据结构网上去看了它的运行原理，分析了几次和参考网上的代码，写出如下内容：

运行结果：

今天就这样了，可能是深度不够，吐不出什么东西来，但是这几天来，一天一个算法，然后练习题目，哪里不懂学哪里。感觉到慢慢在开始学入java底层了。