这是我参与8月更文挑战的第1天，活动详情查看：8月更文挑战
冒泡排序
冒泡排序可能是我们大部分人接触的第一个排序方法，也是最最最基础的算法了。
原理 ：
比较两个相邻的元素，将值大的元素交换到右边
思路 ：
依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
(2)比较第2和第3个数，将小数 放在前面，大数放在后面。
……
(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成
(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
(6)依次类推，每一趟比较次数减少依次
(2)第一趟排序：
第一次排序：10和1比较，10大于1，交换位置 [1,10,35,61,89,36,55]
第二趟排序：10和35比较，10小于35，不交换位置 [1,10,35,61,89,36,55]
第三趟排序：35和61比较，35小于61，不交换位置 [1,10,35,61,89,36,55]
第四趟排序：61和89比较，61小于89，不交换位置 [1,10,35,61,89,36,55]
第五趟排序：89和36比较，89大于36，交换位置 [1,10,35,61,36,89,55]
第六趟排序：89和55比较，89大于55，交换位置 [1,10,35,61,36,55,89]
第一趟总共进行了六次比较，排序结果：[1,10,35,61,36,55,89]
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
}
}
}
复制代码算法分析：
(1)由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数
(2)冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
优化1：（只能在数组前部部分有序的情况下优化）
如果经过一次排序后，剩下未排序的数字已经排列好，无需剩下的多次循环排序；则我们应设定变量来控制终止剩下的循环。
for (int end = array.length - 1; end > 0; end--) {
boolean sorted = true;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sorted = false;
}
}
if (sorted) break;
}
复制代码优化2：（数组中有有序部分优化）
在数组中，有着片段的子数组是有序的，在排序中我们不需要对他进行排列，可以将他视为一个整体进行排列；如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数 。
最后1次交换的位置是6
示例：
for (int end = array.length - 1; end > 0; end--) {
// sortedIndex的初始值在数组完全有序的时候有用
int sortedIndex = 1;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sortedIndex = begin;
}
}
end = sortedIndex;
}
复制代码算法分析：
最坏、平均时间复杂度：O(n2)； 最好时间复杂度：O(n) ；空间复杂度：O(1) ；
优化之后冒泡排序，能快速地将数组内，已经排好序的子数组，不经子数组内部排序，将子数组当成一个整体进行排序；在某个数组中有多个已排好序的子数组，在时间运算上有极大的提升。
如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法
排序前： 5, 1,3?, 4,7,3?
稳定的排序： 1,3?, 3?, 4,5,7
不稳定的排序： 1, 3?, 3?,4, 5,7
对自定义对象进行排序时，稳定性会影响最终的排序效果
冒泡排序属于稳定的排序算法 稍有不慎，稳定的排序算法也能被写成不稳定的排序算法，比如下面的冒泡排序代码是不稳定的
选择排序
在我看来选择排序的冒泡排序有着异曲同工之妙，两者的区别是冒泡排序是遇到比自己大的就进行一次交换，而选择排序是找到此次排序中的最大值之后再进行一次交换，减少了不必要的交换次数。
原理：
1.从序列中找出最大的那个元素，然后与最末尾的元素交换位置 执行完一轮后，最末尾的那个元素就是最大的元素；
2.忽略 1 中曾经找到的最大元素，重复执行步骤 1；
示例：
for (int end = array.length - 1; end > 0; end--) {
int maxIndex = 0;
for (int begin = 1; begin <= end; begin++) {
if (array[maxIndex] <= array[begin]) {
maxIndex = begin;
}
}
int tmp = array[maxIndex];
array[maxIndex] = array[end];
array[end] = tmp;
}
复制代码算法分析：
选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序 ；
最好、最坏、平均时间复杂度：O(n2)，空间复杂度：O(1)，属于不稳定排序 ；
\
堆排序
堆排序的排序方式可以看成选择排序的优化，在未排序部分利用堆的方式来寻找最大值。
原理：
执行流程 ：① 对序列进行原地建堆（heapify）； ② 重复执行以下操作，直到堆的元素数量为 1 ；交换堆顶元素与尾元素 ；堆的元素数量减 1 ；对 0 位置进行 1 次 siftDown 操作
示例：
// 原地建堆
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
while (heapSize > 1) {
// 交换堆顶元素和尾部元素
swap(0, --heapSize);
// 对0位置进行siftDown（恢复堆的性质）
siftDown(0);
}
private void siftDown(int index) {
T element = array[index];
int half = heapSize >> 1;
while (index < half) { // index必须是非叶子节点
// 默认是左边跟父节点比
int childIndex = (index << 1) + 1;
T child = array[childIndex];
int rightIndex = childIndex + 1;
// 右子节点比左子节点大
if (rightIndex < heapSize &&
cmp(array[rightIndex], child) > 0) {
child = array[childIndex = rightIndex];
}
// 大于等于子节点
if (cmp(element, child) >= 0) break;
array[index] = child;
index = childIndex;
}
array[index] = element;
}
复制代码算法分析：
相较于选择排序，在选取最大值时利用了堆的数据结构，降低了复杂度，因为是利用数组原地进行建堆，所以空间复杂度为O(1)
最好、最坏、平均时间复杂度：O(nlogn)，空间复杂度：O(1)，属于不稳定排序 ；
插入排序
插入排序非常类似于扑克牌的排序
原理 ：
① 在执行过程中，插入排序会将序列分为2部分 头部是已经排好序的，尾部是待排序的
② 从头开始扫描每一个元素 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
示例：
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
while (cur > 0 && cmp(cur, cur - 1) < 0) {
swap(cur, cur - 1);
cur--;
}
}
/*
*cmp
* 返回值等于0，代表 array[i1] == array[i2]
* 返回值小于0，代表 array[i1] < array[i2]
* 返回值大于0，代表 array[i1] > array[i2]
*
*swap
*交换
*/
复制代码\
\
插入排序——逆序对
- 什么是逆序对？
数组 <2,3,8,6,1> 的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>，共5个逆序对。
算法分析：
最坏、平均时间复杂度：O(n2)
最好时间复杂度：O(n)
空间复杂度：O(1)
属于稳定排序
当逆序对的数量极少时，插入排序的效率特别高 甚至速度比 O nlogn 级别的快速排序还要快
数据量不是特别大的时候，插入排序的效率也是非常好的
插入排序——优化
原理：
思路是将【交换】转为【挪动】
① 先将待插入的元素备份
② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
③ 将待插入元素放到最终的合适位置
示例：
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
T v = array[cur];
while (cur > 0 && cmp(v, array[cur - 1]) < 0) {
array[cur] = array[cur - 1];
cur--;
}
array[cur] = v;
}
复制代码插入排序——二分搜索优化
插入排序就像在已排列好的数据中，插入一个数值合适，位置合适的数，而我们寻找这个位置的时候就可以使用二分查找（在我的另一篇文章）来找到哪个合适的位置。
原理：
在元素 v 的插入过程中，可以先二分搜索出合适的插入位置，然后再将元素 v 插入
要求二分搜索返回的插入位置：第1个大于 v 的元素位置
如果 v 是 5，返回 2；
如果 v 是 1，返回 0；
如果 v 是 15，返回 7 ；
如果 v 是 8，返回 5
假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) /2
如果 v < m，去 [begin, mid) 范围内二分搜索
如果 v ≥ m，去 [mid + 1, end) 范围内二分搜索
示例：
//排序方法
protected void sort() {
for (int begin = 1; begin < array.length; begin++) {
insert(begin, search(begin));
}
}
/**
* 将source位置的元素插入到dest位置
* @param source
* @param dest
*/
private void insert(int source, int dest) {
T v = array[source];
for (int i = source; i > dest; i--) {
array[i] = array[i - 1];
}
array[dest] = v;
}
/**
* 利用二分搜索找到 index 位置元素的待插入位置
* 已经排好序数组的区间范围是 [0, index)
* @param index
* @return
*/
private int search(int index) {
int begin = 0;
int end = index;
while (begin < end) {
int mid = (begin + end) >> 1;
if (cmp(array[index], array[mid]) < 0) {
end = mid;
} else {
begin = mid + 1;
}
}
return begin;
}
复制代码算法分析：
需要注意的是，使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是 O(n2) ；
我们只是在原有的复杂度上在查找合适位置时，进行了优化原有的时间复杂度没有变化。
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
