KJHの博客

归并排序是建立在归并操作上的一种有效的排序算法，将两个（或两个以上）有序表合并成一个新的有序表。采用分治法，分而治之：分就是将待排序序列分为若干个有序的子序列，每个子序列是有序；合就是把有序的子序列合并为整体有序序列。

这个算法的基本操作是合并两个已排序的表，因为这两个表是已排序的，所以若将输出放到第三个表中时，则该算法可以通过对输入数据一趟排序来完成。将两个有序表合并成一个有序表，成为2-路归并。可知归的前提是子序列是排序好的，我们可以把整体序列递归地分割成一个一个的子序列，当子序列中仅有一个元素时，该子序列自然就是已排序好，然后再不断的进行2-路归并，最终得到整体有序序列。

下面用图演示这一过程

需要说明的是，上面的分割是意识形态的，和前面介绍的堆排序类似，并不是实际的分割，分割过程中，元素在序列中的位置不变，我们仍可以通过数组索引定位元素。

从上面的图解很容易得知，“2-路分割”和 2-路合并，首先需要将整体无序序列进行递归“2-路分割”，直至分割达到有序状态即子序列仅一个元素（这也是递归的终止条件），然后就是合并，将子序列从小到大放入额外暂存单元中，全部归并完毕，这个暂存单元中的元素就是有序的。

1、选择排序

实现思想：首先在未排序序列中找到最小（大）元素，存放在排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。通俗的讲就是从无序区（不同于插入排序，这里的无序区包含所有元素）选一个最小（大）的元素直接放在有序区的最后，即选择一个最小的元素依次放在前面，即选择最小（大）元素就有个逐一比较和交换的过程。

实现步骤：

设数组为a[0…n-1]

1. 初始时，数组全为无序区，为a[0…n-1]。令i = 0；

2. 在无序区a[i…n-1] 中选取一个最小的元素，将其与 a[i] 交换，交换之后a[0…i+1] 就形成了有序区，无序区为a[i+1…n-1]；

3. i++，并重复第 2 步直到 i==n-1，排序完成。

上面的第 2 步是将数据进行交换，但每次只交换一次数据，选取最小元素，是保存最小的元素的索引值，然后交换无序区第一个元素与该索引指定的元素（无序区的最小值）。

1、直接插入排序

基本思想：每次将一个待排序的数据，按其大小插入到前面已经排好序的子序列中的适当位置，直到全部数据插入完成为止。换言之，就是将无序区（第一个元素默认有序）的第一个元素（也就是输入数组的第二个元素）通过与有序区的数据进行比较，然后直接插入到有序区的适当位置，形成更大的有序区，这样有序区扩大了一个元素，无序区缩小了一个元素。以此循环遍历，最终，整个数组就构成了有序区，排序也就完成了。上面的插入并不是交换，而是将该数据前面大于的数据依次后移，然后插入合适位置，构成新的有序区。

设数组为a[0…n-1]。

1. 初始时，a[0] 自成1个有序区，无序区为a[1…n-1]。令i = 1；

2. 将a[i]与前面的有序区进行比较，由后往前依次比较，将大于a[i]的数据依次后移，直至遇到小于a[i] 的数据，就把a[i]插入到该数据的后面，或者直至把有序区比较完毕，a[i]最小，就把a[i]插到最前面，构成新的有序区；其实质就是以无序区的第一个元素依次向前比较。

3. i++，循环2,3，直至i = n-1。

说到算法，不得不提到两个重要的概念：时间复杂度和空间复杂度。时间复杂度跟数据的输入规模 n 密切相关，时间复杂度的计算就是：找到执行次数最多的语句，然后计算语句执行次数的数量级，用大O表示结果。可以把这个输入规模看做是一个变量来理解，如果时间复杂度为O(1)，那个这个 n 就不是一个变量而是一个常量，不管其数值是多少，哪怕是十万级，它的时间复杂度也是O(1)，相反如果这个 n 是一个变量，可能它的最大值就是不过十，那么同样情况下（线性）它的时间复杂度就是O(n)，二次级就是O(n^2)，以此类推。讨论的时间复杂度是最坏情况下的时间复杂度，这就保证了算法的运行时间不会比任何更长。

空间复杂度是对一个算法在运行过程中临时占用存储空间的量度，当一个算法的空间复杂度为一个常量，即占用的临时存储空间不随被处理数据量n的大小而改变时，可表示为O(1)。

另外再说下排序算法的稳定性，通俗的讲就是排序前两个相等的数在序列中的前后位置顺序和排序后它们两个的前后位置顺序相同。如果A[i] = A[j]，A[i] 原来在位置前，排序后A[i] 还是在A[j] 位置前，则是稳定的。这里的前后位置顺序是相对位置（不一定是相邻），排序前A[i] 在A[j] 前面，排序后A[i] 还是在A[j] 前面就是稳定的。

一个图 G = （V，E）由顶点（vertex）集 V 和边（edge）集 E 组成。每一条边就是一个点对（v，w），其中 v，w ∈V。

图的表示
图的存储一般有邻接表和邻接矩阵两种。若图是稠密的，则宜采用邻接矩阵；图是稀疏的，则应改用邻接表。这里我们先讨论图的邻接表存储方式。

先看下面的无向图（图片来源于网络）

​

邻接表形式