189 8069 5689
冒泡排序 O(N^2)就是把一轮排序把每个相邻的数进行大小比较，就是第一个数和第二个数比较，然后交换，第二个数再和第三个数比较，然后交换，就这么两两交换到最后（n-1次）。如果是按照升序来排序的话，然后这样的话一轮排序下来，大的一个数就排到了最后面，每一轮下来都是大的一个数都会被排到最后面，这样就排好序了**（排n轮）**
选择排序O(N^2)就是一轮排序从第一个数到最后一个数中选出一个最小的数(这里也是个比较的过程)，然后和第一个数交换，然后第二轮从第二个数到最后一个数中选一个最小的数和第二个数交换，每轮下来最小的一个数都会被放到最前面，总共通过n-1轮排序，得到一个从小到大排列的有序序列
插入排序O(N^2) 就是认为数组第一个数已经排好顺序 后面待排序的数插入到前面已经排好序的数组中，就是第二个数插入就要和第一个数比较，然后交换，第三个数插入，就和前面两个数依次比较，然后插入。然后后面的每个数都这么依次插入，然后最后一个数插入完后就得到一个有序的数组了，插入排序问题（后面的数越小 移动的次数越多） 所以就提出了希尔排序
希尔排序O(N*logN) 就是先将数据分组 再在组内进行排序，就比如十个数，先分成五组，每两个数一组，两个数之间的步长是5，然后这两个数进行插入排序，小的数排前面，大的数排后面。然后五组再对半分，分成两组，每五个数一组，每个数之前的步长是2，然后对这五个数进行插入排序。最后两组再对半分，分成一组，再进行插入排序，最后得到一个有序数组
快速排序O(N*logN) 先定义一个基准数，一般会把数组中最左边的数当成基准数，然后定义两个指针从两边进行检索。丛右边检索比基准数小的，然后左边检索比基准数大的。如果检索到了，就停下，然后交换这两个元素，然后继续检索。当两个指针相遇的时候，相遇的这个数左边的数都比基准数小，右边的都比基准数小大，然后我们把基准数和相遇的这个数交换。
这是一轮排序，顺序还是没有排好，然后我们可以把左右两边的数据都看成一个新的数组，然后用递归再对这个新数组用同样的方式进行排序，然后就能得到一个有序数组
归并排序 就是递归得将原始数组递归对半分隔，直到不能再分后，就是分到只剩下一个元素，开始从最小的数组向上回溯，依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L2vYgLQc-1670228642706)(https:note.youdao.com/yws/res/5/WEBRESOURCEfc529fca122346c9dedf9a6a9716f505)]
桶/基数排序 将整数按位切割成不同的数字，然后按每个数的位数分别比较。就比如说这堆数里面大的是个三位数
按照个位数进行排序。按序把他们放入相对应的桶内
按照十位数进行排序。按序把他们放入相对应的桶内
按照百位数进行排序。按序把他们放入相对应的桶内
排序后，数列就变成了一个有序序列。
堆排序 1):将待排序的序列先 生成一个树，定义父子结点，父节点parent，子节点2*parent+1，然后比较左右子节点哪个大，用这个大的结点去和父节点进行对比，如果父节点小于子节点，就把父子结点交换，然后利用for循环，让parent=数组长度-1；让parent–，这样就构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中大的元素
2):将堆顶元素和最后一个元素交换，把最后一个元素取出，然后将剩下的节点重新构造成一个大顶堆；
3):重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了
完全二叉树是一种特殊的二叉树。从上到下，从左到右，每一层的节点都是满的，最下边一层所有的节点都是连续集中在最左边。
大顶堆：在完全二叉树的基础上，每个结点的值都大于或等于其左右孩子结点的值
时间空间复杂度1、直接插入排序的时间和空间效率**：**
✪ 时间复杂度:O(n2),空间复杂度：O(1);因为在空间上没有利用什么辅助空间稳定
2、希尔排序的时间跟空间效率：
✪ 时间复杂度:大约O(n1.3),空间复杂度：O(1);因为在空间上没有利用什么辅助空间不稳定
不稳定的原因~假设有两个相同的数字在两个不同的子序列里边，如果每个子序列把小数扔前大数扔后，可能导致两个位置发生先后改变。
✿ 希尔排序注意点：不宜在链式结构上进行实现~因为分割的间隔d的值导致每个子序列的元素之间出现间隔，使用数组有下标可以快速找到哈！
3、冒泡排序的时间跟空间效率：
✪ 时间复杂度:O(n2),空间复杂度：O(1);因为在空间上没有利用什么辅助空间稳定
4、快速排序的时间跟空间效率：
✪ 时间复杂度:O(nlog2n),空间复杂度：O(log2n); ~ ~不稳定
■为什么时间是O(nlog2n)**呢？ —**递归算法耗费时间：O(log2n)
**—**其余数跟中心点进行比较耗费时间: O(n)
■为什么空间是O(log2n)**呢？----快速排序不是原地排序—**递归需要用到栈，而栈的长度取决于调用的深度，平均情况是 O(log2n)，最差情况是O(n)。
不稳定的原因~假设有两个相同的数字，取第一个数为中心点，当比较后会出现low=high的那个位置，导致第一个数放到low=high位置上导致两个数前后顺序发生改变。
5、简单（直接）选择排序的时间跟空间效率：
✪ 时间复杂度:O(n2),空间复杂度：O(1);因为在空间上没有利用什么辅助空间不稳定。
不稳定的原因直接选择排序擂台法【找小，从小到大排序】，假设有两个相同的数字，当第一个数比擂台上的数还小，则替换掉擂台上的数，然后在第二个数的后边又出现了其他比擂台的数替换掉擂台上的数，导致两个数前后顺序发生改变。
6、堆排序的时间跟空间效率：
✪ 时间复杂度:O(nlog2n),空间复杂度：O(1); ~~因为在空间上没有利用什么辅助空间~不稳定
■为什么时间是O(nlog2n)**呢？ —**递归算法耗费时间：O(log2n)
**—**最后一个元素放到根结点后，其余元素位置需要遍历调整: O(n)。
不稳定的原因~调成成大根堆（或小根堆）时数据的调整导致相同的两个数据先后位置发生改变。
✿ 堆排序注意点：不适合待排记录个数较少的情况，对于n较大的文件还是很有效的。
7、归并排序的时间跟空间效率：
✪ 时间复杂度:O(nlog2n),空间复杂度：O(n); ~~稳定
■为什么时间是O(nlog2n)**呢？ —**递归算法耗费时间：O(log2n)趟
**—**所有元素都需要进行归并，每一趟都要合并n个元素: O(n)
8，基数排序（也叫桶排序）的时间跟空间效率：
✪ 时间复杂度:O(k*(n + m)),空间复杂度：O(n+m); ~稳定
●为什么时间是O(k*(n + m))呢？
■ k 是关键字的位数的个数，例如待排数据中的大一个数有三位数（个十百），则k=3；
■ n 是要分配n个数，m是要收集的m个数（m就是桶数，从桶中收集数据）；
●为什么空间是O(n + m)呢？
■ 辅助空间是有m个桶，每个桶的深度是n；
使用建议：3-1*，按时间性能考虑（平均时间性能）*：
■ 时间复杂度O(nlog2n）：快排、堆排、归并特点都用到了递归快排最优
■ 时间复杂度O(n）：桶排
■ 时间复杂度O(n2）：冒泡、直接选择、直接插入特点外层循环进行趟数，内循环比较个数直接插入最优
✿ 注意：当待排记录序列按关键字顺序有序时，直接插入和冒泡排序都能到到的时间复杂度为O(n);而此时对快排是最不好的情况，导致其时间复杂度退化为O(n2);
3-2*，按空间性能（辅助空间）考虑*：
■ 空间复杂度O(1）：冒泡、简单选择、直接插入、希尔、堆排~特点是就地排序
■ 空间复杂度O(log2n）：快排~因为栈所需辅助空间
■ 空间复杂度O(n）：归并、桶排
3-3*，按稳定性考虑*（稳定性~两个相同的数据因排序导致原先的先后顺序发生改变）：
■ 八大排序不稳定算法: 希尔、直接选择、快排、堆排
■ 其中最不稳定算法：快排、堆排，
稳定的排序：冒泡排序，插入排序，归并排序，基数排序。
堆排序public class Test03 {
public static void main(String[] args) {
int[] arr = new int[]{587,956,12,47,30,20,15,11,21,31,57,91,35,120};
for (int p = arr.length-1;p>=0;p--){
sort(arr,p,arr.length);
}
for(int i = arr.length-1; i>=0;i--){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
sort(arr,0,i);
}
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr,int parent,int length){ //传参传入parent
int Child = 2*parent+1;//定义左孩子
while(Child< length){// 判断有没有右孩子，以及左右孩子谁大
int rChild = Child+1;//定义右孩子
if(rChildarr[Child]){//如果右孩子大于左孩子
Child++; //将Child指针指向右孩子
}
//孩子和父结点对比
if (arr[parent]< arr[Child]){
//交换父子结点的值
int temp = arr[parent];
arr[parent] = arr[Child];
arr[Child] = temp;
//交换父子结点
parent = Child;
Child = 2* Child+1;
}else {break;}
}
}
} public class Test07 {
public static void main(String[] args) {
int[] arr = new int[]{4,5,7,3,8,2,4};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right) {
if (left >= right){
return;
}
int base = arr[left];
int i =left;
int j= right;
while (i!=j){
while(arr[j] >= base && i为什么需要树这样数据结构、
1.数组存储方式分析
优点：通过下表方式访问元素，速度快。对于有序数组没还可以使用二分查找提高检索速度。
缺点：如果要检索某一个具体值，效率比较低下
2.链式存储方式分析
优点：在一定程度上对数组存储方式进行优化（比如插入一个节点，只需要将插入节点，链接到链表当中可删除的效率也很好）。
缺点：在进行检索时，效率仍然比较低，比如（检索某个数值，需要从头结点开始遍历）
3.树存储方式分析
能提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度。同时也可以保证数据的插入，删除，修改的速度。
和线性表有很大的区别，线性表的关系是一对一的，而树的节点的对应关系是一对多的
二叉树满二叉树： 一个二叉树，如果每一层的结点数都达到大值，则称这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是(2^k)-1，则它就是满二叉树。
完全二叉树： 是效率很高的数据结构，它是由满二叉树而引出来的。对于深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。注意：满二叉树是一种特殊的完全二叉树。
二叉搜索树1、如果左子树不为空，那么所有的左子树的节点值均小于根节点值。
2、如果右子树不为空，那么所有的右子树的节点值均大于根节点值。
查找
1、如果根节点的数据就是要查找的数据，则返回成功。
2、如果根节点的数据大于要查找的数据，则递归查找左子树。
3、如果根节点的数据小于要查找的数据，则递归查找右子树。
4、如果子树为空，则查找失败。
被称之为AVL树，平衡二叉树可以定义为一颗空树，或者是一颗二叉查找树，在兼备二叉查找树的性质的同时又具有以下的几种特点：
1、平衡二叉树的形态之一是空树，另一种形态是树的左右节点的深度之差不可以超过1。
2、平衡二叉树除了根节点外的左右子树分别也是平衡二叉树，依次类推。
3、二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。
（Red Black Tree） 是一种自平衡二叉查找树，也可以看作是一种特化的平衡二叉树(AVL)，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。红黑树不管是在最坏的情况下或者是最好的情况下，它的插入，查询，删除的时间复杂度都是O(logn)。
1、红黑树的节点是红色或者是黑色。
2、红黑树的根节点是黑色。
3、红黑树的所有叶子都是黑色（叶结点即指树尾端NIL指针或NULL结点）。
4、在红黑树中，如果一个节点是红色，那么它的两个子节点都是黑色。
5、从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
B树（B-tree）是一种自平衡的树，能够保持数据有序，这种数据结构可以让查找数据，顺序访问，插入数据和删除数据等操作都在对数的时间内完成。
B树概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
B树具有以下几种性质：
1、根节点至少有两个子女。
2、每个中间节点都包含k-1个元素和k个孩子。其中m/2<=k<=m
3、每个叶子节点都包含有k-1个元素，其中m/2<=k<=m。
4、所有的叶子节点都位于同一层。
5、每个节点中的元素从小到大排列，节点当中k-1个元素刚刚好是k个孩子包含的元素的值域划分。
B+ 树是一种树数据结构，通常用于关系型数据库(如Mysql)和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。 b+树的非叶子节点不保存数据，只保存子树的临界值(大或者最小)，所以同样大小的节点，b+树相对于b树能够有更多的分支，使得这棵树更加矮胖，查询时做的IO操作次数也更少。
中k-1个元素刚刚好是k个孩子包含的元素的值域划分。
B+ 树是一种树数据结构，通常用于关系型数据库(如Mysql)和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。 b+树的非叶子节点不保存数据，只保存子树的临界值(大或者最小)，所以同样大小的节点，b+树相对于b树能够有更多的分支，使得这棵树更加矮胖，查询时做的IO操作次数也更少。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧