1、排序算法

关于排序算法我就不一一赘述了，建议看下这篇博客，讲的很详细。

常用的排序一般是冒泡排序和快速排序。

冒泡排序的基本思想：对于一组数据，从前往后（或者从后往前）对相邻的两个数据进行比较，如果前面数字比后面数字大，则交换两个数的位置，以此类推直到最后。时间复杂度为O(n^2)。

代码实现：

   /**     * description : 冒泡排序     * @param pData     * @return     */    static void bubbleSort(int[] n){     for (int i = 0; i < n.length-1; i++) {       for (int j = i+1; j < n.length; j++) {          int temp=0;          if (n[i]>n[j]) {            temp=n[j];           n[j]=n[i];           n[i]=temp;      }    }  }}

快速排序基本思想：将一组数据分割成两部分，其中一部分的所有数据都要比另外一部分所有数据要小，然后分别对两部分数据进行快速排序，整个过程用递归进行，直到所有数据是有序的。时间复杂度为O(nlogn)，当n比较大时推荐使用快速排序。

代码实现：

   /**     * description : 快速排序     * @param pData     * @param left     * @param right     * @return     */    static void quicksort(int n[], int left, int right) {        int dp;        if (left < right) {            dp = partition(n, left, right);            quicksort(n, left, dp - 1);            quicksort(n, dp + 1, right);        }    }     static int partition(int n[], int left, int right) {        int pivot = n[left];        while (left < right) {            while (left < right && n[right] >= pivot)                right--;            if (left < right)                n[left++] = n[right];            while (left < right && n[left] <= pivot)                left++;            if (left < right)                n[right--] = n[left];        }        n[left] = pivot;        return left;    } public static void main(String[] args) {  int[] n={13,15,11,25,35,431,55,231,9,1};  quicksort(n, 0, n.length-1);  for (int i = 0; i < n.length; i++) {   System.out.println(n[i]);  }   }

2、递归算法

递归的基本思想：把一个复杂的问题分解成若干个雷同的子问题，直到子问题能直接求解，递归下去从而解决原问题。

常用的递归思想：

1、求一个数的阶乘

 public static int fact(int n)    {        int ans;        if(n==0||n==1)        {            ans=1;        }        else        {            ans=n*fact(n-1);        }        return(ans);    }

例如n=5 则执行else条件

ans=5*fact(4)

fact(4)=4*fact(3)

fact(3)=3*fact(2)

fact(2)=2*fact(1)

fact(1)=1

以此类推ans=5*4*3*2*1=120

2、斐波那契数列  1，1，2，3，5，8，13……

  public static int fibon(int n)    {        int ans;        if(n==0||n==1)        {            ans=1;        }        else        {            ans=fibon(n-1)+fibon(n-2);        }        return(ans);    }

3、数组和链表区别

1）数组是长度是固定的，而且数组内的元素是连续存放的，访问数组元素可以直接通过下标访问，但是插入和删除元素都需要移动后面的元素，效率较低，增加数组元素则超出了数组长度，减少则会造成内存浪费；链表不是固定长度的，它的内部元素不是顺序存储的，而是通过指针关联，因此便于插入和删除元素。

2）数组在栈中分配空间，有程序员分配内存但自由度小；链表从堆中分配空间，自由度大，但申请管理比较麻烦。

4、堆和栈的区别

首先来讲堆和栈是两种数据结构。

栈是一种先进后出的数据结构，也就是最先进去的最后出来，就像往箱子里面放东西一样，要想拿出底下的东西，需要先把上面的东西拿出来。

堆是一种经过排序的树形数据结构，他的存取是随意的，就行书架上的书，随时可以取出或者放进去，不影响其他书。

结合上面说的数组和链表，数组是栈结构，便于查找，但是不便于插入和删减。链表是堆结构，便于插入和删减。

上面说的是数据结构中的堆和栈，要区分的还有堆区和栈区，下面来看一张图：

内存中的栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的。

栈中分配局部变量空间，堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量，全局变量空间的；只读区是分配常量和程序代码空间的；以及其他一些分区。

栈是由程序自动分配自动释放，当可用内存小于所需内存时就会报错栈溢出，所以自由度较小。

堆是由程序员自己申请自己释放，如果没有及时释放，容易造成内存泄漏，自由度较大，但不好管理。

5、二分查找

使用二分查找的前提是数据的顺序是有序的，二分查找的最坏的时间复杂度是O（logn）。也就是说查找的数据在整个数据的开头或者是结尾，最好情况是O（1），也就是正好是中间的值。下面来看下具体实现代码：

/**		 * 二分查找		 * @param n		 * @param l		 * @param r		 * @param query		 * @return		 */		public static int twof(int[] n,int l,int r,int query){			int mid=l+(r-l)/2;			if (query==n[mid]) {				return mid;				}else if(n[mid]>query){				return twof(n,l,mid-1,query);			}else if(n[mid]

除了二分查找还有顺序查找O（n），分块查找，二叉树查找等。