数组和链表的区别?

　　从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。

　　从内存存储的角度看；数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。

　　从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

简述快速排序过程

　　掌握所有常见的排序算法的手写实现，以及复杂度相关细节知识。

　　选择一个基准元素,通常选择第一个元素或者最后一个元素,

　　通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。

　　此时基准元素在其排好序后的正确位置

　　然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

各类排序算法对比（熟练掌握）

　　时间复杂度来说

　　（1）平方阶(O(n2))排序

　　各类简单排序:直接插入、直接选择和冒泡排序；

　　（2）线性对数阶(O(nlog2n))排序

　　快速排序、堆排序和归并排序；

　　（3）O(n1+§))排序,§是介于0和1之间的常数。

　　希尔排序

　　（4）线性阶(O(n))排序

　　基数排序，此外还有桶、箱排序。

　　说明：

　　当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

　　而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

　　原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。