1）原理
n个元素的序列，从第一个数开始，每次比较相邻的两个数，如果符合,就交换，直到把当前的最大数“冒泡”到最上面，我们完成一轮的冒泡趟数；这样总共要
2）代码实现（java）
3）优化
我们知道每一趟的进行，只是为了把当前的最大的数冒泡上去，那如果当前趟数的最大数本身就是在数组的最右边（即本身已经冒泡好了），那我们何必继续该轮冒泡呢？基于这一点，我们可以推出：上一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
解决办法：
代码实现：
1）原理
设要排序的数组是，首先任意选取一个数据（通常选用数组的第一个数）作，然后，，值得注意的是，然后我们就相当于将一个数组分成了两截，这个时候我们可以继续下去，对这两个子数组继续划分，而实现这个，可以用递归。
一趟快速排序的算法是：
1）设置两个变量i、j排序开始的时候：i=0，j=N-1；
2），即base=A[0]；
3）从j（）开始放哨，即由后开始向前搜索()，找到第一个小于base的值，
- 存在就进行交换），然后
- 不存在，哨兵i就会继续放哨，直到，完成一趟快速排序
书本的标准写法：
3）Demo演示
我的：
1）原理
它的工作原理是：第一次从，存放在序列的起始位置，然后以此类推，直到全部待排序的数据元素的个数为零。趟数是n-1趟。是不是很简单啊？
2）代码实现
3）Demo演示
4）评价
首先我们肯定能够知道它的比较次数与数据初始排序状态无关，；。，
交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多但是因为
1）原理
很口语的说法:那这个时候我们，。然后，在里边我们再用找到最小值所在，我们就交换，重复，直到排完数组的数。
那么这个神器是什么呢？那就是——堆，用数组实现的一个有特别属性的完全二叉树，戳我一下详细了解堆的结构
堆分为两种
- 最大堆，双亲结点的值比每一个孩子结点的值都要大。根结点值最大
- 最小堆，双亲结点的值比每一个孩子结点的值都要小。根结点值最小
注意：堆的根结点中存放的是最大或者最小元素，但是其他结点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于根结点 的位置，但是最小的元素则未必是最后一个元素。唯一能够保证的是最小的元素是一个叶结点，但是不确定是哪一个。
基于上面的一些介绍，我们可以知道算法的步骤应该是：
- 1）把输入的数组建立堆的结构，可以神器般速度获取（根结点）最大值（最小值）的所在
- 2）使用直接选择排序将当前的堆获取的最大值（最小值）与当前序列的末尾元素进行交换
- 3）此时我们破坏了堆原有的属性，我们要把剩下的数组序列进行重新建立堆
- 4）回弹第二步，直到所有的数都排好序
所以难点就在于
2）代码实现
5）应用
不仅用于排序算法，还可以应用于频繁选择极值的问题，如优先队列，、Huffman、Prim、Kruskal、Dijkstra、Floyd等算法。
1）原理
非常棒的归并排序讲解，图解
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(nlog n)}（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
原理描述：
作为一种典型的分而治之思想的算法应用，归并排序的实现分为两种方法：
- 自上而下的递归；
- 自下而上的迭代；
2）代码实现
个人比较喜欢递归实现：
当然也得学会迭代法实现：
归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种.分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n，比较操作的次数介于 和。 赋值操作的次数是。归并算法的空间复杂度为：
1）原理
，从开始，将，，找到了，就进去，（给它插入）。完成一个数的插入，继续下一个数。直到最后一个数插入完毕。
简单得跟我们打牌整理牌一样。
2）代码实现
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
该方法实质上是一种分组插入方法
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按，每组中记录的.，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
2）代码实现
？？？？？？？？？？？？？？？？？？？？？？？？？？？
5）评价
希尔排序是非稳定排序算法。不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。，希尔排序时间。希尔排序，因此。但是。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。 本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。 Good?
1）原理
计数排序（Counting sort）是一种。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组用来计数。
简单巧妙的原理，假设有数组A[10]值为：，现在我们，我们就把，这个数组计数器相应的下标都加上或者减去一个定值（delta）能够让我们知道存进来的是数组A中的哪个数(看作映射)，而这个计数器下标里边的数代表该数出现的次数。
这样我们就知道一个数出现的次数是多少了。我们利用了映射——找到最大最小值，建立数组计数器的长度，那我们令delta为0+min；那count[0]存放的是(0+delta)的值出现的个数,即min的个数！
排序过程：就是把计数器里的数一个一个地放回去。
所以就分两步：
- 计数
- 放回排序
2）代码实现
3）Demo
还是上次选择排序的那个数组，我这里使用了降序：
4）评价
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。值得一提它是的排序。
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
1）原理
桶排序是计数排序的升级版。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
2）代码实现
我自己写的使用二维数组实现的：（有点麻烦，因为二维数组在插入数的时候，如果同时进行排序，要移动很多数）这里设置桶数10。当然我们也可以使用函数映射生成桶的个数
一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，要求对这500 万元素的数组进行排序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有**人，501分有***人。
2.大文件的数据排序
在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可（内存限制为2G意思是可以使用2G空间来运行程序，而不考虑本机上其他软件内存占用情况。） 关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。
分析：既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。
思想：将整型的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。
参考资料：百度百科桶排序的应用
2）代码实现
这里演示全是正整数的排序：
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
基数排序有两种方法：
- MSD 从高位开始进行排序
- LSD 从低位开始进行排序
5）基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶（根据位数）
- 计数排序：每个桶只存储单一键值（下标映射实际的数）
- 桶排序：每个桶存储一定范围的数值（根据一个函数映射得到一个桶容纳数的范围）