在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具 - 站长辅助工具 - 脚本之家在线工具
排序算法是非常常见也非常基础的算法，以至于大部分情况下它们都被集成到了语言的辅助库中。排序算法虽然已经可以很方便的使用，但是理解排序算法可以帮助我们找到解题的方向。
算法的稳定性：主要是看同样的输入或者执行过程结果是否一致.
1. 冒泡排序 (Bubble Sort)
冒泡排序是最简单粗暴的排序方法之一。它的原理很简单，每次从左到右两两比较，把大的交换到后面，每次可以确保将前M个元素的最大值移动到最右边。
步骤
从左开始比较相邻的两个元素x和y，如果 x > y 就交换两者
执行比较和交换，直到到达数组的最后一个元素
重复执行1和2，直到执行n次，也就是n个最大元素都排到了最后
复杂度分析
由于我们要重复执行n次冒泡，每次冒泡要执行n次比较（实际是1到n的等差数列，也就是(a1 + an) * n / 2），也就是O(n^2)。 空间复杂度是O(n)。
2. 插入排序（Insertion Sort）
插入排序的原理是从左到右，把选出的一个数和前面的数进行比较，找到最适合它的位置放入，使前面部分有序。
步骤
从左开始，选出当前位置的数x，和它之前的数y比较，如果x < y则交换两者
对x之前的数都执行1步骤，直到前面的数字都有序
选择有序部分后一个数字，插入到前面有序部分，直到没有数字可选择
复杂度分析
因为要选择n次，而且插入时最坏要比较n次，所以时间复杂度同样是O(n^2)。空间复杂度是O(n)。
3. 选择排序（Selection Sort）
选择排序的原理是，每次都从乱序数组中找到最大（最小）值，放到当前乱序数组头部，最终使数组有序。
步骤
从左开始，选择后面元素中最小值，和最左元素交换
从当前已交换位置往后执行，直到最后一个元素
复杂度分析
每次要找一遍最小值，最坏情况下找n次，这样的过程要执行n次，所以时间复杂度还是O(n^2)。空间复杂度是O(n)。
4. 希尔排序（Shell Sort）
https://www.cnblogs.com/chengxiao/p/6104371.html
算法动画视频：数据结构排序算法之希尔排序演示_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
教学算法：编程算法基础第19集-希尔排序-教育-高清正版视频-爱奇艺
希尔排序从名字上看不出来特点，因为它是以发明者命名的。它的另一个名字是“递减增量排序算法“。这个算法可以看作是插入排序的优化版，因为插入排序需要一位一位比较，然后放置到正确位置。为了提升比较的跨度，希尔排序将数组按照一定步长分成几个子数组进行排序，通过逐渐减短步长来完成最终排序。
步骤
计算当前步长，按步长划分子数组
子数组内进行普通的插入排序
步长除以2后继续12两步，直到步长最后变成1
复杂度分析
希尔排序的时间复杂度受步长的影响，具体分析在维基百科。
5. 归并排序（Merge Sort）
归并排序是采用分治法（Divide and Conquer）的一个典型例子。这个排序的特点是把一个数组打散成小数组，然后再把小数组拼凑再排序，直到最终数组有序。
步骤
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
这个实现中加了一个temp，是和原数组一样大的一个空间，用来临时存放排序后的子数组的。
复杂度分析
在merge_array过程中，实际的操作是当前两个子数组的长度，即2m。又因为打散数组是二分的，最终循环执行数是logn。所以这个算法最终时间复杂度是O(nlogn)，空间复杂度是O(n)。
6. 快速排序（Quick Sort）（最最最重要的面试排序了）
快速排序也是利用分治法实现的一个排序算法。快速排序和归并排序不同，它不是一半一半的分子数组，而是选择一个基准数，把比这个数小的挪到左边，把比这个数大的移到右边。然后不断对左右两部分也执行相同步骤，直到整个数组有序。
步骤
用一个基准数将数组分成两个子数组
将大于基准数的移到右边，小于的移到左边
递归的对子数组重复执行1，2，直到整个数组有序
复杂度分析
快速排序也是一个不稳定排序，时间复杂度看维基百科。空间复杂度是O(n)。
7. 堆排序（Heap Sort）
图解排序算法(三)之堆排序 - dreamcatcher-cx - 博客园
堆排序经常用于求一个数组中最大k个元素时。因为堆实际上是一个完全二叉树，所以用它可以用一维数组来表示。因为最大堆的第一位总为当前堆中最大值，所以每次将最大值移除后，调整堆即可获得下一个最大值，通过一遍一遍执行这个过程就可以得到前k大元素，或者使堆有序。
在了解算法之前，首先了解在一维数组中节点的下标：
i节点的父节点 parent(i) = floor((i-1)/2)
i节点的左子节点 left(i) = 2i + 1
i节点的右子节点 right(i) = 2i + 2
步骤
构造最大堆（Build Max Heap）：首先将当前元素放入最大堆下一个位置，然后将此元素依次和它的父节点比较，如果大于父节点就和父节点交换，直到比较到根节点。重复执行到最后一个元素。
最大堆调整（Max Heapify）：调整最大堆即将根节点移除后重新整理堆。整理方法为将根节点和最后一个节点交换，然后把堆看做n-1长度，将当前根节点逐步移动到其应该在的位置。
堆排序（HeapSort）：重复执行2，直到所有根节点都已移除。
简洁版本：
使用临时变量temp
使用temp（）临时变量版本
复杂度分析
堆执行一次调整需要O(logn)的时间，在排序过程中需要遍历所有元素执行堆调整，所以最终时间复杂度是O(nlogn)。空间复杂度是O(n)。
8.基数排序（最难的一种排序了）
基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始, 依次进行一次稳定排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
比如这样一个数列排序: 342 ，58， 576， 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位) http://www.cnblogs.com/sun/archive/2008/06/26/1230095.html
第一次排序(个位):
3 42
5 76
3 56
0 58
第二次排序(十位):
342
356
058
576
第三次排序(百位):
05 8
34 2
35 6
57 6
结果: 58 342 356 576
