- 1、冒泡排序
- 2、选择排序
- 3、插入排序
- 4、希尔排序
- 5、基数排序
- 6、堆排序
- 两个游标，遍历比较大小，每次把一个数据放到正确位置；
- 让游标移动：加循环；
- 冒泡排序核心代码
-
找到数组最小值和待排序数组第一个进行交换
-
i从前到后找最小值；j游标从前到后遍历，确定哪个是待排序数组第一个值
-
定义一个临时空间，待排序数组先放到临时空间，游标向后找，进行比较，小值放入临时空间，最终临时空间是数组最小值；临时空间的最小值与待排序数组数字进行交换
内存要记录临时空间的值和地址 -
选择排序核心代码
-
首先游标i指向待排序数组第一个，i指向的数据将会插入到排序数组当中；
-
排序数组中由两个游标，j和j+1，j和j+1进行比较，j>j+1则进行交换，j和j+1向左移动，直到j指向的数字小于j+1指向的数字，程序停止。
-
j的初始值总是等于i-1
-
插入排序的问题：当我们要插入的数据越小，后移的次数明显增多，效率越低；
-
插入排序核心代码：
-
插入排序的问题：当我们要插入的数据越小，后移的次数明显增多，效率越低；
-
为解决这个问题，采用希尔排序。——>希尔排序：将小的数据放在前边
-
希尔排序流程：
（1）第一轮： 首先两两进行分组，在组内进行插入排序；
-
i游标指向待排序数组第一个，j游标指向待排序数组另一个，两者进行比较，使小值在前面，大值在后；
-
再进行i++操作，j也进行j++，同样待排序数组两者进行比较，使小值在前，大值在后；
-
待排序数组两者之间的距离是步长；步长：数组长度的一半(1/2)
（2）第二轮： 步长是数组长度的1/4
-
同样j和 “j+步长” 之间进行比较；使小在前大在后；然后游标向前移动一个，再进行比较；然后游标再向前移动一个，再进行比较，此时j和 “j+步长” 游标需要向后移动一个步长，进行比较，直到后面待排数组没有数据。
-
“j+步长” 向前移动的距离是一个步长
（3）第三轮： 步长是数组长度的1/8
-
继续进行上述操作，若此时步长为1，则和插入排序步骤一样。
-
最后一次调整也只是微调，相当于解决了插入排序的当我们要插入的数据越小，后移的次数明显增多的问题。
-
希尔排序核心代码：
也可以定义步长：
初始数组：
- 基数排序流程：
（1）先准备好10个桶，排列序号0~9；依次比较个位、十位、百位、……。
（2）根据个位进行排序：
再把数据依次取出：
（3）根据十位进行排序
再把数据依次取出：
（4）重复上述步骤，直到按数组位数最高的一位进行排序，再依次取出：
- 如何实现这些桶：二维数组
1、游标i指向待排序数组第一个；计算出各位数据，放到桶内；
2、同时需要一个桶数据记录器（一维数组），记录每一列插入数据的个数
3、定义一个游标，遍历桶记录器内的数据，知道桶内有多少数据，再将数据取出
4、每次排序注意清空桶记录器的数据 - 基数排序核心代码：
堆排序需要了解完全二叉树和大顶堆小顶堆
1、完全二叉树——>完全二叉树是一种特殊的二叉树，要求数据从上到下、从左到右依次进行平铺
2、大顶堆小顶堆
大顶堆：在完全二叉树的基础之上，每个节点的值都大于等于其左右孩子的值
小顶堆：在完全二叉树的基础之上，每个节点的值都小于等于其左右孩子的值
注：只看父子关系，不看兄弟关系
- 堆排序步骤：
第一步：完全二叉树——>大顶堆；
第二步：堆顶元素和堆底元素进行互换；交换完成之后，堆底元素不再参与构建（有序）；
第三步：继续构建大顶堆，堆顶和堆底互换；
注： 实际并不会在完全二叉树上进行构建，实际上是利用完全二叉树的特点来构建大顶堆 - 完全二叉树的特点：
- 具体如何构建大顶堆：
（1）定义一个parent游标和一个child游标；parent游标从后向前移动，如果当前节点没有子树则直接跳过
注：（6->1->3->0->2->4->7->5 按数组索引从后到前），如果当前节点没有子树则直接跳过
（2）如果当前节点有子树，先让child执行其左子树
（3）判断该节点有没有右子树，如果有，Child游标指向右子树当前最大的值（有比较判断）
（4）当前节点和Child节点的值进行对比，如果当前节点大于child节点的值，parent游标继续向前移动
（5）如果当前节点小于child节点的值，父子节点的值进行交换
（5.1）parent游标指向child游标的位置，child游标的地址=2*child+1
（5.1.1）如果child游标指向空，parent游标继续向前移动
（5.1.2）如果child游标指向不为空，重复第4、5步
注：
游标向后移动是为了保证子树结构的有序性；
- 构建大顶堆伪代码流程：
（1）定义游标p，parent，child，p游标每循环一次，sort方法就入栈出栈一次，parent游标就会重新赋值一次，直到有子树，child指向左子树
注：p只负责在数组做移动来控制整体，parent和child真正进行比较来干活；
（2）实现parent和child的功能；
定义左子树
注：
1）为什么是arr.length：因为child可以等于arr.length-1，也可以写成child<=arr.length-1;
2）不满足child （3）判断有没有右子树，比较左右子树大小，child指向大的
（4）父子节点进行对比交换：父<子—>交换
交换后游标向下移动：parent=child；child=2*child+1；
（5）只要满足child
（6）发现了bug：会死循环，因为if不执行，也没有下一步操作，因此会困在while循环；改正后：
- 堆顶和堆底元素互换
（1）互换完后堆底元素（最大值）不再参与构建
（2）使（构建大顶堆）使用的数组元素长度减1
（3）第二次构建大顶堆，不需要像第一次一样遍历，只要将parent初值赋为0，数组长度减1；
（4）从上面代码可以发现能构建循环，控制（构建大顶堆）使用的数组元素长度
