数据结构常见问题系列(一)

旧城等待， 2022-11-22 10:10 107阅读 0赞

### 文章目录 ###

*   *  1. 数组和链表的区别
     *  2. 简述快速排序
     *  3. 排序算法对比
     *  4. 稳定性
     *  5. 用循环比递归效率高吗？
     *  6. 解决哈希冲突的方法
     *  7. KMP算法
     *  8. B树

## 1. 数组和链表的区别 ##

1). 从逻辑结构来看，数组必须固定长度，数据不能动态增减，即数组的大小一旦定义就不能改变。当数据增加时，可能超过原先定义的元素的个数；当数据减少时，造成内存的浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且方便地插入、输出数据项。  
   2). 从内存存储的角度看，数组从栈中分配空间，对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。  
   3). 从访问方式看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素的时候只能通过线性方式由前到后顺序访问，访问效果比较低。

**关键词：长度、存储、访问**

--------------------

## 2. 简述快速排序 ##

1). 选择一个基准元素,通常选择第一个元素或者最后一个元素。  
   2). 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。  
   3). 此时基准元素在其排好序后的正确位置。  
   4). 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

--------------------

## 3. 排序算法对比 ##

**时间复杂度**

1). 平方阶 ( O ( n 2 ) ) (O(n^\{2\} )) (O(n2))排序：直接插入、直接选择和冒泡排序；  
   2). 线性对数阶 ( O ( n l o g 2 n ) ) (O(nlog2n)) (O(nlog2n))排序：快速排序、堆排序、归并排序；  
   3). 线性阶 ( O ( n ) ) (O(n)) (O(n))排序：基数排序，此外还有桶、箱排序；

说明：

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

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为 ( O ( n 2 ) ) (O(n^\{2\} )) (O(n2))；

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

--------------------

## 4. 稳定性 ##

若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

--------------------

## 5. 用循环比递归效率高吗？ ##

递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。

**1). 递归算法：**

**优点：** 代码简洁、清晰，并且容易验证正确性。

**缺点：** 它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

**2). 循环算法：**

**优点：** 速度快，结构简单。

**缺点：** 并不能解决所有的问题，有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

## 6. 解决哈希冲突的方法 ##

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。

线性探测法、平方探测法、 伪随机序列法、拉链法

--------------------

## 7. KMP算法 ##

在一个字符串中查找是否包含目标的匹配字符串。

--------------------

## 8. B树 ##

根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。