数据结构和算法的概念

数据结构概念（逻辑结构和物理结构）

数据结构概念：把数据元素按照一定的关系组织起来的集合，用来组织和存储数据

数据结构分类：数据结构分为逻辑结构和物理结构两大类

逻辑结构分类：集合结构、线性结构、树形结构、图形结构

a.集合结构：集合结构中数据元素除了属于同一个集合外，他们之间没有任何其他的关系

b.线性结构：线性结构中的数据元素之间存在一对一的关系

c.树形结构：树形结构中的数据元素之间存在一对多的层次关系

d. 图形结构：图形结构的数据元素是多对多的关系

物理结构分类：逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。

a.顺序存储结构：把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的 ，比如我们常用的数组就是顺序存储结构。

b.链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

顺序存储结构--查询块，增删慢

链式存储结构--查询慢，增删块

算法概念

算法概念：根据一定的条件，对些数据进行计算，得到需要的结果

       在生活中，我们如果遇到某个问题，常常解决方案不是唯一的。

       例如从西安到北京，如何去？会有不同的解决方案，我们可以坐飞机，可以坐火车，可以坐汽车，甚至可以步行，不同的解决方案带来的时间成本和金钱成本是不一样的，比如坐飞机用的时间最少，但是费用最高，步行费用最低，但时间最长。

       再例如在北京二环内买一套四合院，如何付款？也会有不同的解决方案，可以一次性现金付清，也可以通过银行做按揭。这两种解决方案带来的成本也不一样，一次性付清，虽然当时出的钱多，压力大，但是没有利息，按揭虽然当时出的钱少，压力比较小，但是会有利息，而且30年的总利息几乎是贷款额度的一倍，需要多付钱。

       在程序中，我们也可以用不同的算法解决相同的问题，而不同的算法的成本也是不相同的。总体上，一个优秀的算法追求以下两个目标：

1. 花最少的时间完成需求；

2.占用最少的内存空间完成需求；

        有关算法时间耗费分析，我们称之为算法的时间复杂度分析，有关算法的空间耗费分析，我们称之为算法的空间复杂度分析。

数据结构与算法的关系

       数据结构就像是一个工具，算法使用数据结构这一工具完成一定的运算，但是要合理使用，不能拿一个铁锤拧螺丝

经典案例

排序

冒泡排序

排序原理：

1.比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。

2.对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值

代码实现：

import java.util.Arrays;
public class BubbleSort {
  public static void main(String[] aaa) {
    int[] a=new int[]{5,2,4,3,1,8,6,7};
    sort(a);
    System.out.print(Arrays.toString(a));
  }
  public static void sort(int[] a) {
    for(int i=0;i<a.length-1;i++)
    {     
      for(int j=0;j<a.length-1-i;j++)
      {
        if(a[j]>a[j+1])
        {
          int temp=a[j];
          a[j]=a[j+1];
          a[j+1]=temp;
        }
      }
    }
  }
}

时间复杂度分析：

       冒泡排序使用了双层for 循环，其中内层循环的循环体是真正完成排序的代码，所以，

我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。

在最坏情况下，也就是假如要排序的元素为{6,5,4,3,2,1} 逆序，那么：

元素比较的次数为： (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

元素交换的次数为： (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

总执行次数为：(N^2/2-N/2)+(N^2/2-N/2)=N^2-N;

按照大 O 推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为 O(N^2)

选择排序

排序原理：

每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引

交换第一个索引处和最小值所在的索引处的值

代码实现：

import java.util.Arrays;
public class SearchSort {
  public static void main(String[] aaa) {
    int[] a=new int[]{5,2,4,3,1,8,6,7};
    sort(a);
    System.out.print(Arrays.toString(a));
  }
  public static void sort(int[] a) {
    //第一层循环，控制遍历次数
    for(int i=0;i<a.length-1;i++)
    {
      //min记录最小的数
      int min=a[i];
      //minNum记录最小的数的下标，用于下面的交换
      int minNum=i;
      //第二层循环，遍历比较出最小值
      for(int j=i+1;j<a.length;j++)
      {
        if(min>a[j])
        {
          min=a[j];
          minNum=j;
        }
      }
      //将最小值移动到最前面
      a[minNum]=a[i];
      a[i]=min;
    }
  }
}

时间复杂度分析：

选择排序使用了双层 for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数：

数据比较次数：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

数据交换次数：N-1

总执行次数为：N^2/2-N/2+ （ N-1 ） =N^2/2+N/2-1;

根据大 O 推导法则，保留最高阶项，去除常数因子，时间复杂度为 O(N^2)

插入排序

排序原理：

1.把所有的元素分为两组，已经排序的和未排序的；

2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；

3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

代码实现：

import java.util.Arrays;
public class InsertSort {
  public static void main(String[] aaa) {
    int[] a=new int[]{1,3,12,5,3,123,5,4676,54};
    System.out.println(Arrays.toString(a));
    sort(a);
    System.out.println(Arrays.toString(a));
  }
  public static void sort(int[] a)
  {
    for(int i=1;i<a.length;i++)
    {
      for(int j=i;j-1>=0;j--)
      {
        if(a[j-1]>a[j])
        {
          int temp=a[j-1];
          a[j-1]=a[j];
          a[j]=temp;
        }
        else break;
      }
    }
  }
}

时间复杂度分析：

插入排序使用了双层 for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复杂度，主要分析一下内层循环体的执行次数即可。

最坏情况，也就是待排序的数组元素为 {12,10,6,5,4,3,2,1} ，那么：

比较的次数为： (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

交换的次数为： (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

总执行次数为：(N^2/2-N/2)+(N^2/2-N/2)=N^2-N;

按照大 O 推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为 O(N^2)

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序原理：

1.首先设定一个分界值，通过该分界值将数组分成左右两部分。

2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

切分原理：

    把一个数组切分成两个子数组的基本思想：

1.找一个基准值，用两个指针分别指向数组的头部和尾部；

2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；

3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；

4.交换当前左边指针位置和右边指针位置的元素；

5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止；

代码实现：

import java.util.Arrays;
public class QuickSort {
  public static void main(String[] args) {
    int[] a=new int[]{50,23,88,35,65,53,90,13,52,42,16,18,73,25,77,66};
    System.out.println(Arrays.toString(a));
    sort(a,0,a.length-1);
    System.out.println(Arrays.toString(a));
  }
  public static void sort(int[] a,int b,int e)
  {
    if(b>=e) return;
    int i=b;
    int j=e;
    while(i<j) {
      if(a[i]>a[i+1]) {
        int temp=a[i];
        a[i]=a[i+1];
        a[i+1]=temp;
        i++;
      }else {
        int temp=a[j];
        a[j]=a[i+1];
        a[i+1]=temp;
        j--;
      }
    }
    sort(a,b,i-1);
    sort(a,i+1,e);
  }
}

时间复杂度分析：

快速排序的一次切分从两头开始交替搜索，直到 left 和 right 重合，因此，一次切分算法的时间复杂度为 O(n),但整个快速排序的时间复杂度和切分的次数相关。

最优情况：每一次切分选择的基准数字刚好将当前序列等分。

如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn);

最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分 n 次，所以，最坏情况下，快速排序的时间复杂度为 O(n^2);

平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们可以用数学归纳法证明，快速排序的时间复杂度为 O(nlogn);