软件设计师 知识点拾遗 数据结构

1. 2015年下半年第64题和65题

• 插入排序：其工作原理是将数组分为已排序和未排序的两部分，逐个将未排序元素插入到已排序部分的正确位置上。这种排序方法适用于小规模数据或者基本有序的数据。
• 归并排序：归并排序是分治法的典型案例，其基本过程如下所述：将待排序的线性表不断地切分为若干个子表，直到每个子表只包含一个元素，这时，可以认为这是一个有序表。随后将子表两两合并，每合并一次就会产生一个新的且更长的有序表，如此循环往复即完成了排序。归并排序一般用于对大规模且需要稳定排序的数据进行排序。
• 快速排序：快速排序也是一种应用分治法的排序方式，它首先从数组中选取一个基准值（这一基准值通常是待划分数组的中位数），随后将数组重新排列，使得基准值左侧的元素全部小于它而其右侧的元素全部大于它。然后继续对左右两侧子数组分别重复上述过程，直到子数组长度为1或者0。快速排序适合对大规模乱序数据排序。
• 计数排序：计数排序会统计每个关键字的出现次数，通过累加计数确定元素的位置。这一排序方法适用于关键字范围小且密集的数据。

2. 2015年上半年第61题

  简单选择排序的基本方法是:①从待排序序列中，找到关键字最小的元素;②如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换;③从余下的 N-1个元素中，找出关键字最小的元素，重复②步，直到排序结束。