㈠ 常见排序算法归纳
排序算法一般分类：
比较两个相邻的元素，将值大的元素交换至右端。
依次比较两个相邻的数，将小数放到前面，大数放到后面
即在第一趟：首先比较第1个数和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此一直继续下去，直到比较最后两个数，将小数放前，大数放后。然后重复第一趟步骤，直到所有排序完成。
第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较。
第二趟完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较。
依次类推......
输出结果：
冒泡排序的优点： 每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
用时间复杂度来说：
从一个数组中随机选出一个数N，通过一趟排序将数组分割成三个部分，1、小于N的区域 2、等于N的区域 3、大于N的区域，然后再按照此方法对小于区的和大于区分别递归进行，从而达到整个数据变成有序数组。
如下图：
假设最开始的基准数据为数组的第一个元素23，则首先用一个临时变量去存储基准数据，即 tmp=23 ，然后分别从数组的两端扫描数组，设两个指示标志： low 指向起始位置， high 指向末尾。
首先从后半部分开始，如果 扫描到的值大于基准数据 就让 high-1 ，如果发现有元素比该基准数据的值小，比如上面的 18 <= tmp ，就让 high位置的值赋值给low位置 ，结果如下：
然后开始从前往后扫描，如果扫描到的值小于基准数据就让 low+1 ，如果发现有元素大于基准数据的值，比如上图 46 >= tmp ，就再将 low 位置的值赋值给 high 位置的值，指针移动并且数据交换后的结果如下：
然后再开始从前往后遍历，直到 low=high 结束循环，此时low或者high的下标就是 基准数据23在该数组中的正确索引位置 ，如下图所示：
这样一遍遍的走下来，可以很清楚的知道，快排的本质就是把比基准数据小的都放到基准数的左边，比基准数大的数都放到基准数的右边，这样就找到了该数据在数组中的正确位置。
然后采用递归的方式分别对前半部分和后半部分排序，最终结果就是自然有序的了。
输出结果：
最好情况下快排每次能恰好均分序列，那么时间复杂度就是O(nlogn)，最坏情况下，快排每次划分都只能将序列分为一个元素和其它元素两部分，这时候的快排退化成冒泡排序，时间复杂度为O(n^2)。
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
将一个数据插入到 已经排好序的有序数据 中
第一趟排序：
用数组的第二个数与第一个数( 看成是已有序的数据 )比较
第二趟排序：
用数组的第三个数与已是有序的数据 {2,3} (刚才在第一趟排的)比较
在第二步中：
...
后面依此类推
输出结果：
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
举例：数组 int[] arr={5,2,8,4,9,1}
第一趟排序 ： 原始数据： 5 2 8 4 9 1
最小数据1，把1放在首位，也就是1和5互换位置，
排序结果： 1 2 8 4 9 5
第二趟排序 ：
第1以外的数据 {2 8 4 9 5} 进行比较，2最小，
排序结果： 1 2 8 4 9 5
第三趟排序 ：
除 1、2 以外的数据 {8 4 9 5} 进行比较，4最小，8和4交换
排序结果： 1 2 4 8 9 5
第四趟排序 :
除第 1、2、4 以外的其他数据 {8 9 5} 进行比较，5最小，8和5交换
排序结果： 1 2 4 5 9 8
第五趟排序：
除第 1、2、4、5 以外的其他数据 {9 8} 进行比较，8最小，8和9交换
排序结果： 1 2 4 5 8 9
输出结果：
归并排序（merge sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
比如我们对 [8,4,5,7,1,3,6,2] 这个数组进行归并排序，我们首先利用分治思想的“分”将数组拆分。
输出结果：
㈡ 常见查找和排序算法
查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。
改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。
适用条件：
二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。
循环实现
递归实现
待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。
归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
归并方法将数组中两个已经排序的部分归并成一个。
将一个大数组分成两个小数组去求解。
因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。
先归并那些微型数组，然后成对归并得到的微型数组。
取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 大的元素。
该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。
堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。
堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。
在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。
类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。
将新元素放到数组末尾，然后上浮到合适的位置。
从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。
一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。
对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。
当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。
实间复杂度N*K
快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。
㈢ O（n2）排序算法的总结
最近在慕课网上学习了O（n2）时间复杂度的相关算法，总算是对这些算法的优缺点有了详细的特点。其实对于任何的算法，没有优点和缺点，而是有相应的特点。所以我们应该结合不同的排序环境来选择不同的排序算法，从而达到在实现时间和执行效率上的平衡。这是因为，越是简单的排序算法，实现起来肯定是越容易，而且出现BUG的概率也不会太大。相反，复杂算法可能效率更高，但是出现问题的可能性也会更大。下面，我就结合O（n2）时间复杂度的四个经典排序算法，为您详细讲解这四个算法的特点。
定义：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
图示说明：
源码实现：
分析：通过选择排序的图示和源码我们可以看出来，选择排序要进行两次循环，而且最关键的是内层循环在每一次执行时都是全部执行完的。那我们有没有办法让内层循环不用每次都执行完呢？方法肯定是有的，这就是冒泡排序。
定义：冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
图示说明：
源码实现：
分析：从图示和源码可以看出来，从执行次数上来说，冒泡排序是比选择排序的循环次数更少的。那是不是就可以说，如果待排序的数组中元素比较合适，冒泡排序在时间复杂度上是不是会比选择排序更好呢？真的是这样的吗？
其实不是的，经过多次测试验证，冒泡排序基本上是比选择排序的时间复杂度要差的，这是为什么呢？从源码中我们可以很明显的看出来，虽然冒泡排序是比选择排序执行次数少了，但是交换的次数明显增多了，而如果你对计算机程序指令的实现原理只要有一个基本的认识，就应该知道交换动作比赋值动作是需要更多指令操作的。所以说，最终冒泡排序大部分情况下，比选择排序的时间复杂度都要高。
既然交换动作这么消耗资源，那有没有一种方法，即能够减少内层循环的执行次数，又可以减少甚至是无需交换操作呢？这就要请出插入排序了。
定义：插入排序（Insertion Sort）的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
图示说明：
源码实现：
分析：从图示和源码可以看出来，插入排序（优化后的）是没有交换操作的，而且对于内层循环来说，如果待排序的元素是比较大的值，那内层循环执行的次数会非常的少。因此，如果原始数据基本上是有序的，那使用插入排序的效率会非常的高。在O（n2）级别的排序算法还可以再优化吗？如果可以从哪里优化呢？下面我们来介绍希尔排序，正是这个排序算法的提出，使得排序算法打破了O（n2）时间复杂度的禁锢。
定义：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该算法的基本思想是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序算法便终止。
对于希尔排序来说，最关键的就是增量该如何选取。这个增量该怎么确定，这还真是个数学难题，至今没有解答。但是通过大量的实验，还是有个经验值的。我们的例子给出的增量选取公式是：h = 3 * h + 1，下面请看图示说明。
图示说明：
源码实现：
分析：从插入排序中我们知道，插入排在待排序数组基本有序时，插入排序的算法效率会非常高，所以我们可以这样认为，希尔排序的最终思想就是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
而希尔排序的效率之所以很高，就是因为这个基本思想确实很有用：即当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。而当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。
对于增量的选取，可以称得上是一种魔法。在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
总结：上面就是四种经典O（n2）级别排序算法的相关说明。其实在各种场合下选择排序和冒泡排序基本上是不会使用的，因为使用场景基本没有。而对于插入排序和希尔排序来说，在待排序数据基本有序的情况下，使用场景还是有的，比如一些日志文件中存储的日志，可能大部分的日志记录都是基于时间排序，只是在某些极端情况下导致一些日志晚存储了导致时间不一致。
我是徐建航， 这是我写的第31篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。