一、冒泡排序：
上学时接触的第一个排序算法，代码都能随时背下来，不过还是再默写一遍吧。
过程也简单，是能想起来的最直观的排序算法。
1.1--->擦，记错了！记了一个假的冒泡。妈的，容易记错。
这个算是简单选择排序的前身。
这个最简单直白。拿当前位置的值和后面的值比较大小，交换位置，每走一趟，确定一个最小的。
void fake_bubbleSort(int *arr, int lengh) {
for (int i = 0; i < lengh-1; i++) {
for (int j = i+1; j < lengh; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
比较的次数1+2+3+。。+（n-1）。所以时间复杂度O（n平方）
1.2--->冒泡排序
挨个两两比较相邻的值，交换位置，最后把大值放到最后。像气泡一样慢慢飘上去。
1.2.1--->从后往前排。
每外层循环走一趟，排好序的值放到前面。
n个数，比较n-1次就行了，因为最后一次就剩一个数了，相当于已经排好序了。
从后往前，每次 j 都是从最后的位置 length-1 开始，内循环走一趟，得到一个最小的数，放到 i 的位置上。i 位置上的值就可以不参与后面的循环比较了。
终止条件j > i，因为此时i前面的已经排好序了，没必要再去比较了。取j和j前面的值比较，即j-1位置。如果 j=0，j-1=-1，数组就越界了。所以不能写成 j >=i
void bubbleSort_back(int *arr, int lengh) {
for (int i = 0; i < lengh-1; i++) {
for (int j = lengh-1; j > i; j--) {
if (arr[j] < arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
1.2.2--->从前往后排
同理。每外层循环走一趟，排好序的值放到最后。
内循环 j 每次都是从0位置开始。
void bubbleSort_front(int *arr, int lengh) {
for (int i = 0; i < lengh-1; i++) {
for (int j = 0; j < lengh-1-i; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
1.3--->冒泡排序的优化
对于比如[2, 1, 3, 4, 5, 6]这样的数组，冒泡排序比较一次就得出结果了，但是还是会往下执行。所以，可以做简单优化。
设置一个状态status，初始值等于1.
外层循环在status=1的情况下才执行，如果status=0，说明已经得到结果了，没必要继续执行了。
每次内层循环之前，就改变status=0，循环比大小。
如果if不执行，说明i后面的值已经符合要求了。终止了外层循环，排序结束。
如果if执行了，重制status=1，可以让外层循环继续执行。
1.3.1-->从后往前方式的优化
void bubbleSort_back_beauty(int *arr, int lengh) {
int status = 1;
for (int i = 0; i < lengh-1 && status == 1; i++) {
status = 0;
for (int j = lengh-1; j > i; j--) {
if (arr[j] < arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
status = 1;
}
}
}
}
1.3.1-->从前往后方式的优化
同理，就不写了。
二、简单选择排序
简单选择排序跟我记错的那个假冒泡类似。那个写法应该放到这里做对比，不过为了提醒自己还是放在开头了。
那个假冒泡写法，每比较一次符合要求，就去交换一下值，通过多次交换交换，得到想要的。
其实，如果开始就把当前值当作最小值，最小值的位置就是 i ，通过每次比较，每当符合要求，就更新最小值的位置信息。最后交换一次就够了。
相比假冒泡，只是交换的操作少了，比较的次数一样多。
简单选择排序相当于假冒泡的优化。
void selectSort (int *arr, int lengh) {
int min;
for (int i = 0; i < lengh-1; i++) {
min = i;
for (int j = i+1; j < lengh; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
三、快速排序
经典算法，没什么可说的，看了忘，忘了看，还是再写一遍吧。
流程：取第一个数值当作基准值。（这个值可以有其他优化方法去取）
while循环，先从右边走，直到遇到比它大就停下；
while循环，再从左边走，知道遇到比它小就停下；
此时交换两侧停止时的值。
直到外层大while循环终止执行，此时i=j。
i位置就是基准值，i左边的都小于基准，i右边的都大于基准，使用递归，分别执行左右两侧范围内的数组。
void quickSort(int *arr, int left, int right) {
if (left >= right) {//递归终止条件
return;
}
int i = left;
int j = right;
int flag = arr[i];
while (i < j) {
while (i < j && arr[j] >= flag) {
j--;
}
while (i < j && arr[i] <= flag) {
I++;
}
if (i < j) {//说明此时i和j还没相遇，交换完位置后，外层while循环继续执行。
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 循环结束，此时i=j。i左边的数都小于等于flag，右边的都大于等于flag
// i停留的位置，arr[i]一定是小于flag的。所以把flag插在i位置上
arr[left] = arr[I];
arr[i] = flag;
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
为什么一定要从右边开始while循环？
quickSort
基准取第一个，如果从左边开始，如图：首先i会在7的位置停下，j也在7的位置停下，此时把基准值插在i位置上，结果是71269.不符合预期。
如果从右边开始while循环，结果是12679，符合预期。
不管从哪边开始，最后都要把i位置和基准位置的值做交换。
两个小while按顺序执行，肯定是第一个先把条件打破，此时i=j，第二个while就不执行了。此时i停留的位置是符合第一个while循环条件的。
如果从左边开始的话，最后i=j打破循环条件，此时停留的位置的值是大于基准值的，此时交换，会把大值放左边，不符合预期。
如果基准取的最后一个值，就要从左边开始循环了。最后一步交换i位置和基准位置的值，需要做相应的修改，：arr[left]变arr[right] 了。就是这么回事。
arr[right] = arr[I];
arr[i] = flag;
所以规则就是：从基准对面开始while循环。如果想从左边开始while，基准就选最右边的数。
注：今天 28号，继续看书继续敲。
请了一天假去医院拔智齿，上午折腾一上午，结果花了三百多，就检查了一下,拍了个牙齿的X光照片。就诊的人太多，我只能排到下周了。下午没事，再看会书。
四、直接插入排序
如果把一个数插入到一个排好序的数组里，直接比较这个数组最后一个数和当前数值的大小，如果比它小，说明当前数已经最大了，直接放最后，如果比它大，就循环倒序比较大小，直到找到比它小的位置，把它插入这个位置。（大概是这么个意思）
但是本来就是解决排序的问题，怎么可能有拍好序的数组？这时把数组里第一个数当作一个数组，就像相当于一个排序的数组。毕竟一个元素的数组也是数组。
😄第零步，没有操作，此时第一个数字就相当于排好序了。因为就一个数字，没什么顺序可去排。所以直接从i=1开始循环。
😄第一步，拿第二个数字和它前面的数字比，即第一个数字，如果比第一个小，两者交换位置，前2个就排好序了。如果比它大，就不动，此时前两个也相当于排好序了（虽然没操作）。
😄第二步，拿第三个数字和它前面的数字比，即第二个数字，如果比第二个大，因为第一个第二个已经排好序了说明它是最大，不操作，相当于排好了。如果比第二个小，说明需要把它移动到前面，此时第二个数字是最大的，把它移动到第三，然后把第三移动到第二，就是交换顺序。交换完，接着往前比较，直到循环终止。
😄第三步。。。同上。。。
void insertSort(int *arr, int length) {
for (int i = 1; i < length; i++) {
if (arr[i] < arr[i-1]) {
int temp = arr[i];//保存当前i位置数值
int j = i-1;
while (arr[j] > temp) {
//每次执行，会造成j和j+1的值重复，相当于j往后移动了一位。数组里少了i位置的值，不过没影响，它保存到temp里了
arr[j+1] = arr[j];//j的值往后移动
j--;
}
//执行完while，i的值找到了它的位置
arr[j+1] = temp;//把数值重复的位置插入temp
}
}
}
适用于数据已经大致排好序的数组。
五、希尔排序
这个是以人名命名的方法，感觉比前几个更屌些。
简单来说就是对插入排序的升级版。插入排序如果对于数据量大并且没有大体上的排序，时间复杂度就高了。
希尔排序就跟把整个数组分成了好几组，然后对每组进行插入排序，这样数据大致按顺排列，小的在前，大的在后。然后分组少一些，再对每组插入排序，最后分成一组，即当前数组，最后进行一次插入排序。
比如长度是10的数组，第一次10/2=5，分五组；第二次5/2=2，分两组，最有2/2=1，分一组，就结束了。5、2、1就是增量序列。所以又叫缩小增量排序。
void shellSort(int *arr, int length) {
for (int gap = length/2; gap > 0; gap /=2 ) {//到gap=1结束
//gap5，2，1
for (int i = gap; i < length; i++) {
if (arr[i] < arr[i-gap]) {
int temp = arr[i];
int j = i-gap;
while (arr[j] > temp) {
arr[j+gap] = arr[j];
j-=gap;
}
arr[j+gap] = temp;
}
}
}
}
核心代码还是插入排序代码，两者比较相似。
代码中，对每组进行插入排序，没有直接对每组依次进行操作，而是在整个数组上同时操作。比如第一次gap=5这次循环，相当于分了五组，对每组插入排序，内层循环第一个是i=5，插入排序比较的是5-gap=0，此时操作的是第一组。然后i++，i=6，插入排序比较的是6-gap=1，此时操作的是第二组，依次类推。直到最后后一组结束后，i++，此时i的范围在第一组，就去操作第一组。一次for循环，相当于把每个数组都处理一次。当然也可以完全处理完一组，再去处理第二组，写法稍微不同。原理都一样。核心都是分组，然后对每组进行插入排序。
六、堆排序
Log：无聊的周日，好难啊，生活难，算法也难。人生苦短，就这么一秒一秒的过去，钱和女人（事业和爱情），一个也没有。看到曾经喜欢的女孩的旅游照，鸡儿更加难受😣，怅然若失就是这个感觉吧。生活就是这么苦逼，隔壁的哥们好像没工作？从来都是躺着玩手机，都是这么艰难。
6.1、🐂🍺
聪明的人就是这么吊，为了把排序的时间复杂度从n平方降低一些，想出来通过二叉树来排序，真是🐂🍺。Floyd和Willianm（弗洛伊德和威廉？）这两人还发明了“堆”的概念。
6.2、完全二叉树
和满二叉树比较，相同位置的节点编号一样。看起来就是：从上到下，一层铺满，再铺下一层。从左到右，先铺左节点，再铺右节点。所以铺满的话就是满二叉树，没铺满的话，只能是最后一层没满。
常用的性质：
1、深度是k，则最多有2的k次方个-1节点。（通过简单的数列的和就可以得到）
2、除了最后一层，每层有2的(k-1)次方个节点。
3、根节点从1开始排序，第n个节点，它的父节点是第n/2个。如果根节点从0开始排序，它的父节点是第n/2-1个。（堆排序计算父节点位置用的上这个）
完全二叉树这个样子的⬇️：
根节点从0开始.png
根节点从1开始.png
6.3、堆
大概也就是完全二叉树的结构？其实也不了解，以后再专门看看堆的概念，再完善这个。分为大顶堆和小顶堆。大顶堆就是父节点的值大于子节点。小顶堆就是父节点的值小于子节点。
长这样⬇️
大顶推和小顶堆.png
6.4、堆排序
如果想升序排序，使用大顶推。（下面都是以大顶堆为例）
根据大顶堆的特点，每个父节点都大于子节点。所以根接节点，就是第一个值肯定是最大的，交换第一节点和最后一个节点，就把最大值放到最后了，此时堆的结构被破坏了，已经不是大顶堆了。这个时候再操作除了最后一个最大值剩余的节点，使其再重新生成大顶堆。
⚠️所以核心就是生成大顶堆。-->建堆
/**
调整堆，处理每个子树
*/
void heapAdjust(int *arr, int index, int length) {
int temp = arr[index];//记录当前根节点
for (int j = index*2; j < length; j*=2) {
if (arr[j] < arr[j+1]) {//比较左右子节点大小
j++;
}
if (temp > arr[j]) {//根节点与子节点比大小
break;//如果根节点大，就直接结束循环。
}
arr[index] = arr[j];//把大的子节点的值赋值给根节点。此时根节点和一个子节点的值相同。
index = j;//记录重复值的那个子节点。也就是for循环下一次的根节点
}
arr[index] = temp;//处理重复值的子节点
}
当前节点序号是index，它的左节点序号就是j=index * 2，右节点序号就是j+1；
通过比较左右节点大小，定位到他俩中大的那个，并用j值记录；
然后比较当前节点index的值和它子节点，如果index的值已经最大，说明此时以index为根节点的小二叉树已经符合大顶堆的规则，它已经是最大值了，后面就没必要判断了，直接break，跳出for循环；
如果index的值不是最大，就把子节点的最大值赋值给它，此时有j和index的值重复，for走了一次，index的值=j，记录当前变化的子节点；
此时j的序号是index的子节点的需要，然后j=j*2，这是为了处理以子节点为根节点的小二叉树，也就是处理下一层，使其符合大顶堆；
最后for循环结束，把index的那个值给index位置。
其实就是：for循环一遍，拿个index位置的值temp，和它的左右子树比较，找到比它大的最大的子树，两者交换值。for循环一次就是为了找到最大值，继续循环下去，是为了维持大顶堆结构。
如果没有使用到break，就说明最后一定会有交换值的操作，会破坏子树的大顶堆结构。所以继续循环，index值一直记录每次循环的根节点的编号，temp一直记录根节点的值。所以最后直接赋值。
🤔为什么要用break终结for循环？不怕它的孙子树重孙树有比它大的值吗？因为大顶堆的的生成就是从下往上走，从最后一个小叉开始处理，就保证了下层的节点值一定比上层的值小。
下面的排序代码，第一个for循环就是生成大顶堆。
/**
堆排序
*/
void heapSort(int *arr, int length) {
for (int i = length/2-1; i >= 0; i--) {///从最后一个子树开始调整，生成大顶堆
heapAdjust(arr, i, length);
}
for (int i = length-1; i > 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapAdjust(arr, 0, length-1);
}
}
第一个for循环，从完全二叉树的最后一个节点开始处理。整个二叉树从0开始编号，所以最后一个节点的父节点序号就是length/2-1
从最后一个叉倒着处理（编号从上到下，从左到右。调整大小，就从下到上，从右到左），每处理一个节点，就确保父节点的值肯定大于子节点，也就解释了为什么可以用break。
整个for结束，此时生成了大顶堆。建堆完成。
第二个for循环，依次交换第一个和最后一个节点的值，此时除了根节点的值不符合大顶推，其余的节点还是符合大顶堆，所以只调整0位置，节点已经数量减了1。
⚠️完事。就是🐂🍺，把数组映射到完全二叉树，根据完全二叉树的节点的编号特点，找到数组中想要的位置的值。就有了堆的概念，堆的根节点就是想要的值。每次调整完数组，利用堆的规则，调整剩下的数据，使其依旧是一个大顶堆。🐂🍺 🐂🍺 🐂🍺
网友评论