2016考研计算机：数据结构核心考点之排序算法
计算机一直是现在的热门专业，每年都有很多从事这方便工作的人，也有很多考研的人。考研计算机的专业课是全国统考科目，包括四个科目，知识点还是很多的，下面一起来看一下考研计算机数据结构核心考点之排序算法。各类排序算法的特点及比较
几种主要的排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、Shell排序、堆排序等。
冒泡排序算法思想：
将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。
选择排序算法思想：
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
插入排序算法思想：
经过i-1遍处理后,L己排好序。第i遍处理仅将L插入L的适当位置，使得L又是排好序的序列。
快速排序算法思想：
快速排序的基本思想是基于分治策略的。对于输入的子序列L，如果规模足够小则直接进行排序，否则分三步处理：1. 分解(Divide)：将输入的序列L划分成两个非空子序列L和L，使L中任一元素的值不大于L中任一元素的值。2. 递归求解(Conquer)：通过递归调用快速排序算法分别对L和L进行排序。3. 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L和L都排好序后不需要执行任何计算L就已排好序。
归并排序算法思想：
分而治之(divide - conquer)。每个递归过程涉及三个步骤：1.分解，把待排序的n个元素的序列分解成两个子序列，每个子序列包括 n/2 个元素。2. 治理，对每个子序列分别调用归并排序MergeSort，进行递归操作。3. 合并，合并两个排好序的子序列,生成排序结果。
Shell排序算法思想：
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
堆排序算法思想：
用大根堆排序的基本思想：1.先将初始文件R建成一个大根堆，此堆为初始的无序区。2.再将关键字最大的记录R(即堆顶)和无序区的最后一个记录R交换，由此得到新的无序区R和有序区R，且满足R.keys≤R.key。3. 由于交换后新的根R可能违反堆性质，故应将当前无序区R调整为堆。
计算机是一门很博大精深的科目，包含的内容千变万化，能学的东西也数不胜数。通过上面的各类排序算法的特点及比较，考生就能更好的比较着复习好排序算法。
页:
[1]