各种排序算法2
桶排序
桶排序(Bucket sort)也是所谓的箱排序,是一个排序算法,各种原理是将数组分到有限数量的桶里,每个桶再个别排序,(有可能是在使用别的排序算法,或者递归的方式继续使用桶排序),最后依次把各个桶中的记录列出来得到有序序列.桶排序是鸽巢排序的一种.当要排序的数组内的数值是均匀分配的时候桶排序使用线性时间O(n)
原理
核心思想就是大问题化小
基数排序
实现
（1）通过键值得各个位的值，将要排序的元素分配至一些桶中，达到排序的作用
（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定排序法
（3）基数排序是桶排序的扩展
将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
步骤
- 确定数组中的最大元素有几位
- 创建0-9个桶(桶的底层是队列)所有的数字元素都是0-9的10个数组构成
- 依次判断元素的各位,10位至max位,存入对应的桶中,出队,存入原数组直至max轮结束输出数组
注意
基数排序是对传统桶排序的扩展,速度很快
基数排序是经典的以空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError（内存溢出）。
基数排序是相对稳定的.
基数排序的空间复杂度为o(n+k) n为数组长度,k为通的数量,一般来说n>k
假如排序的数据可以分为k个关键字(可以理解为数据的长度,或者是几位数),基数排序的时间复杂度是 O(d*2n)的人d要远远小于2n,因此基本上还是线性级别的
堆排序
堆是一种叫做完全二叉树的数据结构,可以分为大根堆小根堆,而堆排序就是继续这种结构产生的一种排序算法
完全二叉树
若二叉树的深度为h,除h层外,其它各层的节点数都到达最大个数,低h层所有节点都连续几种在最左边,这就是完全二叉树
完全二叉树是由满二叉树印出来的.对于深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点-对应时称之为完全二叉树
满二叉树定义:如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
1、叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1;
2、出于简便起见,完全二叉树通常采用数组而不是链表存储。
3、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
4、完全二叉树第i层至多有2(i-1)个节点，共i层的完全二叉树最多有2i-1个节点。
5、只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
6、对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个。
二叉堆解析
简介
二叉堆是完全二元树或者是近似完全二元树，它分为两种：最大堆和最小堆。
二叉堆一般都通过"数组"来实现。数组实现的二叉堆，父节点和子节点的位置存在一定的关系。有时候，我们将"二叉堆的第一个元素"放在数组索引0的位置，有时候放在1的位置。当然，它们的本质一样(都是二叉堆)，只是实现上稍微有一丁点区别。
假设"第一个元素"在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：
(01) 索引为i的左孩子的索引是 (2*i+1);
(02) 索引为i的左孩子的索引是 (2*i+2);
(03) 索引为i的父结点的索引是 floor((i-1)/2);
假设"第一个元素"在数组中的索引为 1 的话，则父节点和子节点的位置关系如下：
(01) 索引为i的左孩子的索引是 (2*i);
(02) 索引为i的左孩子的索引是 (2*i+1);
(03) 索引为i的父结点的索引是 floor(i/2);
添加
当向最大堆中添加数据时：先将数据加入到最大堆的最后，然后尽可能把这个元素往上挪，直到挪不动为止！
将85添加到[90,80,70,60,40,30,20,10,50]中后，最大堆变成了[90,85,70,60,80,30,20,10,50,40]。
删除
假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要执行的步骤如下：
从[90,85,70,60,80,30,20,10,50,40]删除90之后，最大堆变成了[85,80,70,60,40,30,20,10,50]。
如上图所示，当从最大堆中删除数据时：先删除该数据，然后用最大堆中最后一个的元素插入这个空位；接着，把这个“空位”尽量往上挪，直到剩余的数据变成一个最大堆。
排序
排序分为俩个部分
- 初始化堆
- 交换数据
初始化堆
在堆排序算法中，首先要将待排序的数组转化成二叉堆。
下面演示将数组{20,30,90,40,70,110,60,10,100,50,80}转换为最大堆{110,100,90,40,80,20,60,10,30,50,70}的步骤。
堆排序 - 如果天空不死 - 博客园 (cnblogs.com)
第二部分是交换数据
在将数组转换成最大堆之后，接着要进行交换数据，从而使数组成为一个真正的有序数组。
交换数据部分相对比较简单，下面仅仅给出将最大值放在数组末尾的示意图。
上面是当n=10时，交换数据的示意图。
当n=10时，首先交换a[0]和a[10]，使得a[10]是a[0...10]之间的最大值；然后，调整a[0...9]使它称为最大堆。交换之后：a[10]是有序的！
当n=9时， 首先交换a[0]和a[9]，使得a[9]是a[0...9]之间的最大值；然后，调整a[0...8]使它称为最大堆。交换之后：a[9...10]是有序的！
依此类推，直到a[0...10]是有序的。
时间复杂度
堆排序的时间复杂度是O(N*lgN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过lg(2N)。因此，遍历一趟的时间复杂度是O(N)，而遍历次数介于lg(N+1)和lg(2N)之间；因此得出它的时间复杂度是O(N*lgN)。
堆排序稳定性
堆排序是不稳定的算法，它不满足稳定算法的定义。它在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序也可能发生变化。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
计数排序
实现
- 根据待排序集合中最大元素和最小元素的差值范围，申请额外空间；
- 遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
- 对额外空间内数据进行计算，得出每一个元素的正确位置；
- 将待排序集合每一个元素移动到计算得出的正确位置上。
先假设 20 个数列为：{9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9}。
让我们先遍历这个无序的随机数组，找出最大值为 10 和最小值为 0。这样我们对应的计数范围将是 0 ~ 10。然后每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。
比如第一个整数是 9，那么数组下标为 9 的元素加 1，如下图所示。
第二个整数是 3，那么数组下标为 3 的元素加 1，如下图所示。
继续遍历数列并修改数组......。最终，数列遍历完毕时，数组的状态如下图。
数组中的每一个值，代表了数列中对应整数的出现次数。
有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。比如统计结果中的 1 为 2，就是数列中有 2 个 1 的意思。这样我们就得到最终排序好的结果。
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
性能
死机复杂度(n+k)
空间复杂度
o(k)
稳定性:稳定
1.当数列最大最小值差距过大时，并不适用于计数排序
比如给定 20 个随机整数，范围在 0 到 1 亿之间，此时如果使用计数排序的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。
2.当数列元素不是整数时，并不适用于计数排序
如果数列中的元素都是小数，比如 3.1415，或是 0.00000001 这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。
正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。