排序概念：就是将一串记录按照其中某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：通俗的将就是数据元素不发生有间隔的交换，例如：
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能一次加载到内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
注意：以下的排序默认排升序。默认待排序列为：2，5，1，3，8，6，9，4，7，0，6
2. 插入排序把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
2.1 直接插入排序1. 思想：
对于一个元素，将其与前面元素进行比较，将其插入到合适的位置。
排升序：将待排元素依次与序列中元素从右往左比，若待排元素小，则继续往前比，找到合适位置插入，原来元素的位置按顺序往后搬移。
2. 画图说明：
说明：第一个元素默认它有序，所以从第二个元素开始进行比较然后插入，5比2大，继续下一个，将1依次比较插入2前面，将3依次比较插入5前面，8比5大，不用管，继续下一个，将6依次比较插在8面，9比8大，不用管，将7依次比较，插在8前面，将0依次比较插在1前面，将6依次比较插在7前面，插入完成。
3.代码展示：
结果：
4.特性总结：
时间复杂度：循环嵌套，O(N^2)，最优情况：当序列接近有序，插入的元素比较少，为O(N)
空间复杂度：不借助辅助空间，O(1)
稳定性：数据元素不发生有间隔的交换，稳定
应用场景：数据量小，接近有序
2.2 希尔排序（缩小增量排序）1. 思想：
选一个整数为数据元素的间隔，将间隔相同的数据元素分为一组，分别对这些组进行插入排序，间隔减小，重复上述操作，当间隔减少到1的时候，数据元素即排好序了。
2. 画图说明：
说明：gap为间隔，这里依次将gap=4，2，1，先把间隔为4的数据元素用插入排序排好序，再利用插入排序排gap=2 的数据元素，依次重复上述操作，即可。
3. 代码展示：
结果：
4. 特性总结：
希尔排序是对直接插入排序的优化。
当gap>1时都是预排序，目的是让数组元素接近有序，当gap==1时，数组已经接近有序了，这样插入排序将会很快，整体而言，达到了优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。
gap的取法有多种，最初shell提出取gap=n/2，gap=gap/2，直到gap=1，后来，Kunth提出取gap = [gap/3]+1。在Kunth所著的《计算机程序设计技巧》第3卷中，利用大量的实验统计资料得出，当n很大时，关键码的平均比较次数和对象平均移动次数大约在n^1.25到1.6n^1.25范围内，这是利用直接插入排序作为子序列排序方法的情况下得到的。
故时间复杂度暂记为：O(N^1.25)~O(1.6N^1.25)
空间复杂度：没有借助辅助空间，O(1)
稳定性：数据元素发生了有间隔的交换，不稳定
应用场景：数据比较随机
3. 选择排序每一次从待排数据元素中选出最小（最大）的元素，存放在序列的起始（末尾）位置，直到全部待排序的数据元素全部排完。
3.1 直接选择排序1. 思想：
思路1：
找出序列中的最大的元素，若它不在序列的末尾，将它与末尾元素交换位置，依次循环。
思路2：
每次找元素的时候，找一个最大的和一个最小的，最大的和最后一个交换位置，最小的和第一个交换位置，依次循环
2. 画图说明：
思路1：
说明：先找到序列的最大元素与序列最后一个元素交换，序列的最后的位置朝前移一个，再找新序列的最大元素再与最后一个交换位置，依次循环。
思路2：
说明：这种方法是一次找两个元素，跟上面那种本质上一样，只是一次交换了两个元素，将最大的与最后一个交换，将最小的与第一个交换
3. 代码展示：
4：特性总结：
时间复杂度：找元素，交换元素是循环嵌套，O(N^2)
空间复杂度：没有借助辅助空间，O(1)
稳定性：数据元素存在有间隔的交换，不稳定
缺陷：找最大元素或者最小元素的时候重复比较
3.2 堆排序1. 思想：
堆排序是利用堆积树（堆）这种数据结构设计的一种算法，它是选择排序的一种，它是通过堆来进行选择数据。
注意：排升序，建大根堆，排降序，建小根堆。
堆排序分为两部分：建堆，利用向下调整建堆，再利用堆删除的思想排序。
向下调整：
前提：要调整的节点的两个左右子树都已满足堆的特性
方法：建大堆，将根的元素与左右孩子较大的元素交换，建小堆，将根的元素与左右孩子较小的元素交换
堆删除思想：
将堆顶元素与最后一个元素交换位置
堆中有效元素减少一个
再对堆顶元素向下调整
2. 画图说明：
因为数据元素多，二叉树的图看着不太清晰，所以我用以下序列：0，5，3，4，1，2
建堆：
利用堆删除思想排序：
3. 代码展示：
结果：
4. 特性总结：
时间复杂度：n个元素进行比较，而且太向下调整，调整的深度为完全二叉树的深度，故时间复杂度为：O(NlogN),logN是log以2为底的N
空间复杂度：没有借助辅助空间，O(1)
稳定性：元素发生了有间隔的交换，不稳定
应用场景：求前k个最小或者最大，可以和其他排序结合起来增加效率
4. 交换排序基本思想就是根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
4.1 冒泡排序1. 思想：
依次将序列元素进行比较，若array[i]>array[i+1],交换两个元素的位置，直到最后一个元素，从中可以得出，每躺冒泡只能确定一个元素的位置，若序列有n个元素，则需要进行n-1躺冒泡，因为序列最后一个元素的位置不用确定。
从比较的次数可以看出：第一躺比较的次数为n-1，第二躺的比较次数为n-2.....即每趟冒泡比较的次数在递减，即比较次数是为n-1-i，i为冒泡的趟数。
2. 画图说明：
3. 冒泡排序的优化：
从上图可以看出第10躺冒泡没有进行，因为序列已经有序，即数据元素不在发生交换。
优化：在每趟进行的开始给一个标记isChage=false，如果该躺冒泡发生了元素交换，将isChange=true，在每趟冒泡完进行判断，如果是Change==false，即没有发生交换，说明序列已经有序，即不用在继续冒泡，直接返回即可。
4. 代码展示：
结果：
5. 特性总结：
时间复杂度：冒泡的趟数，每趟的比较次数，O(N^2)
空间复杂度：不借助辅助空间，O(1)
稳定性：数据元素虽然发生了交换，但是没有间隔交换，稳定
4.2 快速排序4.2.1. 思想
快速排序是Hoare提出的一种二叉树结构的交换排序方法。
基本思想为：任取待排元素序列中的某个元素作为基准值（这里我们取最右侧元素为基准值），按照该基准值将序列划分为两个区间，左侧比基准值小，右侧比基准值大，再分别用快速排序递归排左区间和右区间。
参考代码：
故只要实现分割方法即可。
4.2.2 三种分割方式
1. Hoare法
思想：在左边找比基准值大的，右边找比基准值小的，两个交换位置，最后将较大一侧的第一个元素与基准值交换位置。
画图说明：
参考代码：
2. 挖坑法
思想：将基准值存入key中，基准值的位置为第一个坑位，在左侧找比基准值大的，放到第一个坑位上，此时这个元素的原始位置又形成了一个新的坑位，再从右侧找比基准值小的，放到前面的坑位上，依次循环，即将序列分割为两部分。
画图说明：
参考代码：
3. 前后标记法
思想：给两个标记cur，pre，pre标记cur的前一个，cur开始标记第一个元素，依次往后走，cur小于区间的右边界，如果cur小于基准值并且++pre不等于cur交换cur与pre位置的元素，最后交换++pre与基准值位置的元素。
画图说明：
参考代码：
4.2.3 快速排序的优化
快速排序的优化：对基准值的选取进行优化，这样做是为了选取的基准值尽可能的将区间的左右侧分的均匀一点儿。
优化方法：三数取中法取基准值，三数：区间的中间元素，最左侧元素，最右侧元素，取它们三个的中间值。
参考代码：
具体与之前代码结合方式，我这里选取一种分割方法来进行优化：
参考代码：
4.2.4 快速排序的非递归方式
非递归的快速排序借助栈这一数据结构
参考代码：
4.2.5 快速排序的特性总结
时间复杂度：有比较，递归，O(NlogN)
空间复杂度：存在递归，递归的深度为完全二叉树的深度，O(logN)
稳定性：数据元素发生有间隔的交换，不稳定
应用场景：数据凌乱且随机
5. 归并排序1. 思想：
归并排序是将两个有序序列进行合并，但是我们拿到是一个数组，所以得先将数组递归均分为两部分，再将两部分进行合并。
2. 画图说明：
递归均分：
从下往上合并：
3. 代码展示：
4. 非递归的归并排序
给一个间隔，用间隔来表示区间
参考代码：
5. 特性总结：
时间复杂度：O(NlogN)
空间复杂度：借助了辅助空间，为辅助数组的大小，O(N)
稳定性：数据元素不发生有间隔的交换，稳定
应用场景：适合外部排序
6. 计数排序（非比较类型的排序）1. 思想：
计数排序又称鸽巢原理，是对哈希直接定址法的变形应用
步骤：
统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中
2. 画图说明：
3. 代码展示：
4. 性能总结：
时间复杂度：O(N)
空间复杂度：O(M),M为数据范围的大小
稳定性：数据元素没有进行有间隔的交换，稳定
应用场景：数据元素集中在某个范围
7. 排序算法总结 排序方法最好平均最坏空间复杂度稳定性插入排序O(n)O(n^2)O(n^2)O(1)稳定希尔排序O(n)O(n^1.3)O(n^2)O(1)不稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定堆排序O(n*log(n))O(n*log(n))O(n*log(n))O(1)不稳定冒泡排序O(n)O(n^2)O(n^2)O(1)稳定快速排序O(n*log(n))O(n*log(n))O(n^2)O(log(n))不稳定归并排序O(n*log(n))O(n*log(n))O(n*log(n))O(n)稳定以上就是Java实现基本排序算法的示例代码的详细内容，更多关于Java排序算法的资料请关注七叶笔记其它相关文章！
