基本排序方法原理(冒泡,快排，直接选择排序，堆排序，直接插入排序，希尔，归并)

排序

基本概念：

内部排序：整个排序过程不需要访问外存便能完成
外部排序：参加排序的记录数量很大，整个排序过程不可能在内存中完成
就地排序：所需的辅助空间不依赖于问题的规模n，即辅助空间为O(1)
稳定排序：假定在待排序列中，存在多个相同的元素，若经过排序后，相同元素的相对次序保持不变，即在原序列中 ri=rj， ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
master公式：

排序1：冒泡排序(bubble sort)

已知一组无序数据a[0]、a[1]、……a[n-1]，需将其用冒泡排序按升序排列。

思路：

首先比较a[0]与a[1]的值，若a[0]大于a[1]则交换两者的值，否则不变。再比较a[1]与a[2]的值，若a[1]大于a[2]，则交换两者的值，否则不变。以此类推。。。最后比较a[n-2]与a[n-1]的值。这样处理一轮后，a[n-1]的值一定是这组数据中最大的。

再对a[0]~a[n-2]以相同方法处理一轮，则a[n-2]的值一定是a[0]~a[n-2]中最大的。以此类推。。。

这样共处理 n-1 轮后a[0]、a[1]、……a[n-1]就以升序排列了。

升序排序实例：

可以看到5个元素组成的序列，经过4轮交换共计10次比较。比较次数公式为：n * (n-1) / 2 。

算法评价：

优点：如果不是故意去交换相等的元素位置，这个算法是绝对稳定的排序算法。

缺点：时间复杂度固定为O(n^2) 。第一、二、三轮，2和3两个元素重复比较了3次，可通过快排改善。

排序2：快速排序(quick sort)

设要排序的数组是A[0]……A[n-1]。

思路：

首先任意选取一个数据作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
然后再按此方法对这其中一部分数据进行快速排序，这是递归调用。
再按此方法对另一部分数据进行快速排序，这也是递归调用。

一趟快速排序算法及其实例：

设置两个变量 i、j，排序开始的时候：i=0，j=n-1；
以第一个数组元素作为关键数据，赋值给 pivot，即 pivot =A[0]；
从 j 开始,由后开始向前搜索(j--)，找到第一个小于 pivot 的值A[j]，将 A[j] 和 A[i] 互换（互换保证了 A[j] > A[i]，也就是保证了要趋向于前方的元素都小于 pivot )；
从 i 开始,由前开始向后搜索(i++)，找到第一个大于pivot 的A[i]，将 A[i] 和 A[j] 互换（互换保证了 A[j] > A[i]，也就是保证了后方的关键码都大于 pivot ）
重复第3、4步，直到 i=j 。

第一步中, A[4]=2与pivot比较并发生交换，经过此操作，原来靠后的元素2跑到了原先靠前的元素2前方，所以快速排序不是稳定的排序算法。

持续移动 i，到第4步的时候，元素5大于pivot发生交换，让5放在pivot的后面。

该到移动 j 的时候了，元素9显然大于pivot，第5步所示，所以 j 继续向前移动。

j此时已经与i重合了，所以while循环终止，至此完成了第一轮迭代。

完成了第一轮迭代后，再就是对pivot前的区间再次执行上述操作，然后再对pivot后的区间执行上述操作。

快排和冒泡的直观比较：

上面这个例子，快速排序第一轮经过了5次比较，2次交换，使得Pivot将整个排序序列分割成两个独立的区间，前面都小于Pivot，后面都大于Pivot；前面区间只需要1次比较，0次交换即可完成；后面区间只需要1次比较，1次交换就可完成，因此总的比较次数为7次，交换次数为3次。

而冒泡排序呢，由上节我们知道它需要10次比较，4次交换才能完成排序。

快排算法评价：

最好情况：如果每次划分产生的区间大小都为n/2(如上例pivot=3将序列分成的前后区间长度相同)，算法运行就很快得多，此时的时间复杂度为 O(nlogn)。

最坏情况：退化为了冒泡排序，时间复杂度为O(n*n)。

平均情况：平均情况和最好情况的时间复杂度都为O(nlogn)，只不过平均情况的常数因子可能大一些，有关详细分析，请查阅相关资料。

排序3：直接选择排序(Straight Select Sorting)

基本思想：

第一次从R[0]~R[n-1]中选取最小值，与R[0]交换；

第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，

第 i 次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，总共通过n-1次，得到一个按关键码从小到大排列的有序序列。

升序排序的例子：

待排序列 3 2 5 9 2

在直接选择排序中，共需要进行 n-1 轮，每轮必发生一次交换，每轮需要进行 n-i 次比较 (1<=i<=n-1)，总的比较次数等于 (n-1) + (n-2) + ... + ( n-(n-1) )

算法评价：

优点：可以看到算法是稳定的，空间复杂度为 O(1) 。

缺点：时间复杂度固定为O(n^2)，不过堆排序可以优化时间性能。

排序4：堆排序(Heapsort）

利用二叉树(堆), 对直接选择排序改进的一种算法。在逻辑结构上是按照二叉树存储结构，在物理存储上是连续的数组存储，利用数组特点来快速定位指定索引的元素。

二叉树基本概念：https://blog.csdn.net/cocoiehl/article/details/80959150

基本概念：

n个关键字序列 K0，K2，…，K(n-1) 称为堆（Heap），当且仅当该序列满足如下性质：

Ki <= K( 2i + 1 ）且 Ki <= K( 2i + 2 ) ( 0≤i≤ (n/2)-1），称为小根堆；

Ki >= K( 2i + 1）且 Ki >= K( 2i +2 ) ( 1≤i≤ (n/2)-1），称为大根堆。

基本思想：

堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即 R[PARENT[i]] >= R[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。小根堆与之类似，每个节点的值都不小于父节点的值，最小值出现在堆顶处。

堆排序是如何工作的：

以大根堆排序为例，即要得到非降序序列。

先将初始文件R[0..n-1]建成一个大根堆，此堆为初始的无序区。
再将关键字最大的记录R[0]（即堆顶）和无序区的最后一个记录R[n-1]交换，由此得到新的无序区 R[0..n-2] 和有序区 R[n-1]，且满足 R[0..n-2] ≤ R[n-1]
由于交换后新的根R[0]可能违反堆性质，故应将当前无序区R[0..n-2]调整为堆。然后再次将R[0..n-2]中关键字最大的记录R[0]和该区间的最后一个记录R[n-2]交换，由此得到新的无序区R[0..n-3] 和有序区R[n-2..n-1]，且仍满足关系R[0..n-3] ≤ R[n-2..n-1]。
重复步骤2和步骤3，直到无序区只有一个元素为止。

应用堆排序得到升序排序的例子：

待排序列 3 2 5 9 2

第一步，我们需要构建大根堆，为了构建大根堆，我们再温习下刚才的堆排序的基础知识，首先以上待排序列的物理存储结构和逻辑存储结构的示意图如下所示，

构建初始堆是从length/2 - 1，即从索引1处关键码等于2开始构建，2的左右孩子等于9, 2，它们三个比较后，父节点2与左孩子9交换，如下图所示：

接下来从索引1减1等于0处，即元素3开始与其左右孩子比较，比较后父节点3与左孩子节点9交换，如下所示：

因为索引等于 0 了，所以构建堆结束，得到大根堆，第一步工作结束，下面开始第二步调整堆，也就是不断地交换堆顶节点和未排序区的最后一个元素，然后再构建大根堆，下面开始这步操作，交换栈顶元素9（如上图所示）和未排序区的最后一个元素2，如下图所示，现在排序区9成为了第一个归位的，

接下来拿掉元素9，未排序区变成了2,3,5,2，然后从堆顶2开始进行堆的再构建，比较父节点2与左右子节点3和5，父节点2和右孩子5交换位置，如下图所示，这样就再次得到了大根堆，

再交换堆顶5和未排序区的最后一个元素2，这样5又就位了，这样未排序区变为了2,3,2，已排序区为 5,9，交换后的位置又破坏了大根堆，已经不再是大根堆了，如下图所示，

所以需要再次调整，然后堆顶2和左孩子3交换，交换后的位置如下图所示，这样二叉树又重新变为了大根堆，再把堆顶3和此时最后一个元素也就是右孩子2交换，

接下来再构建堆，不再赘述，见下图。

算法评价：

堆排序的时间开销，主要由建立初始堆和反复重建堆这两部分构成，堆排序的平均时间复杂度是O(nlogn) 。堆排序是就地排序，空间复杂度为O(1）。

通过上面的例子，可以看到两个元素2的相对位置会发生变化，所以堆排序是不稳定的排序方法。

堆排序算法不大适合数据量较少的情况，因为光构建初始堆就要进行很多次比较。

排序5：直接插入排序(straight insertion sort）

基本思想：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序，直到无序表内所有元素插入为止。

首先在当前有序区R[0..i-1]中查找R[i]的正确插入位置 k(0≤k≤i-1)；

然后将R[k．．i-1]中的记录均后移一个位置，腾出 k 位置上的空间插入R[i]。

直接插入排序举例：

仍然用待排序列 3 2 5 9 2

可以看到共经4轮操作，有些轮需要找到元素的合适位置，同时将(插入点到有序区末尾)元素依次向后移动一个位置，有些轮不需要移动元素，直接将待插入元素插入到有序区最后一位。

算法评价：

可以看到，直接插入排序是稳定的排序算法。

如果目标是把n个元素的序列进行升序排序，那么采用插入排序存在最好情况和最坏情况。

最好情况：序列已经是升序排列，在这种情况下，需进行（n-1）次比较操作即可。

最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次，且要进行元素后移。

插入排序算法平均时间复杂度为O(n^2），比较次数越多，后移元素越多，特别是当数据总量庞大的时候，但是可以用链表解决数据移动的问题(优化方法：希尔排序)。

排序6：希尔排序(shell sort), 也称缩小增量排序

算法思想:

先取一个正整数 d1<n，把所有序号相隔 d1 的数组元素放一组，两组分别进行直接插入排序，
然后取 d2< d1，重复上述分组和直接插入排序操作；
直至di = 1，即所有记录放进一个组中排序为止。

非降序排序举例：

仍用待排序列 3 2 5 9 2

进行非降序排序操作，一般的初次取序列的一半为增量，以后每次减半，直到增量为1，

在第一轮中，选取增量为2，即分为两组，第一组为 [3 5 2] ，另一组为 [2 9 ] ，分别对这两组做直接插入排序，第一组插入排序的结果为[2 3 5]，第二组不动，这样导致的直接结果是原来位于最后的2经过第一轮插入排序后，跑到最头里了，这样两个2的相对位置发生改变了，所以希尔排序不是稳定的排序算法。

再经过第二轮排序，此时的增量为1，所以一共只有一组了，相当于直接插入排序，9后移1步，5插入到原9的位置。

算法评价

希尔排序的时间复杂度为 O(logn * logn * n)(怎么理解？？)，没有快速排序算法O(n*logn)快，因此中等大小规模表现良好，不是大规模数据排序的最优选择。

但是比直接插入排序 O(n^2）复杂度算法快得多，并且希尔排序非常容易实现，算法代码短而简单。

希尔排序性能与所选取的分组长度有很大关系。只对特定的待排序序列，可以准确地估算元素的比较次数和移动次数。想要弄清元素比较次数和移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。

排序7：归并排序(merge sort)

它是建立在归并操作上的一种有效的排序算法，该算法是分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

算法的核心概念---二路归并

若将两个有序表合并成一个有序表，称为二路归并。

归并过程

比较 a[i] 和 b[j] 的大小，若 a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到 r[k] 中，并令i 和 k 分别加上1；否则将第二个有序表中的元素b[j]复制到r[k] 中，并令 j 和 k 分别加上1；
如此循环下去，直到其中一个有序表取完；
然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标t的单元。

二路归并例子演示

初始状态时，a序列[2,3,5]和b序列[2,9]为已排序好的子序列。现在利用二路归并，将a和b合并为有序序列 r，初始时，i指向a的第一个元素，j指向b的第一个元素，k初始值等于0。说明，r中最后一个元素起到哨兵的作用，灰色显示。