直接插入排序每一趟从待排序序列中取出一个值然后将其插入好已排序的序列中默认第一个值是有序的void Insert_Sort(int arr[], int len) { for (int i 1; i len; i)//控制的是趟数 { int tmp arr[i]; int j i - 1; for (; j 0; j--)//控制的是待排序列下标 { if (arr[j] tmp) { arr[j 1] arr[j]; } else { break; } } arr[j 1] tmp; } } void Show(int arr[], int len) { for (int i 0; i len; i) { printf(%d, arr[i]); } printf(\n); } int main() { int arr[] { 2,7,1,8,5,0,9 }; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); Show(arr, len); Insert_Sort(arr, len); printf(排序后); Show(arr, len); }直接插入排序的优化待插入值怎么找到其适合的插入位置二分法希尔排序Shell排序选择排序每一趟从待排序序列中找出最小值所在位置然后将其和待排序序列第一个值所在位置进行交换void Intersect_Sort(int arr[], int len) { for (int i 0; i len-1; i) { int min i; int j; for (j i1; j len; j) { if (arr[j] arr[min]) { min j; } } if (min ! i) { int tmp arr[min]; arr[min] arr[i]; arr[i] tmp; } } } void Show(int arr[], int len) { for (int i 0; i len; i) { printf(%d, arr[i]); } printf(\n); } int main() { int arr[] { 2,7,1,8,5,0,9 }; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); Show(arr, len); Intersect_Sort(arr, len); printf(排序后); Show(arr, len); }冒泡排序每一趟从左到右两两比较如果左边大于右边值则交换相当于每一趟就可以将待排序序列中的最大值通过两两比较搬运的方式挪动到最后面len个值需要len-1void Bubble_Sort(int arr[], int len) { for (int i 0; i len-1; i)//控制的是趟数 { for (int j 0; j 1 len -i; j)//控制的是这一趟中对于排序序列的从前向后两两比较 { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } } void Show(int arr[], int len) { for (int i 0; i len; i) { printf(%d, arr[i]); } printf(\n); } int main() { int arr[] { 2,7,1,8,5,0,9,6 }; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); Show(arr, len); Bubble_Sort(arr, len); printf(排序后); Show(arr, len); }冒泡排序的优化怎么知道这一趟跑完后数据已经完全有序加一个标签如果一趟跑完发现两两比较过程中没有左边大于右边的情况的发生则说明所有值已经完全有序了后续就不用再跑了//冒泡排序的优化 加标签 怎么知道这一趟跑完之后数据已经完全有序 void Bubble_Sort(int arr[], int len) { for (int i 0; i len - 1; i)//控制的是趟数 { bool tag true;//标签申请在内部for循环里 for (int j 0; j 1 len - i; j)//控制的是这一趟中对于排序序列的从前向后两两比较 { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; tag false; } } if (tag true) break; } } void Show(int arr[], int len) { for (int i 0; i len; i) { printf(%d, arr[i]); } printf(\n); } int main() { int arr[] { 2,7,1,8,5,0,9,6 }; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); Show(arr, len); Bubble_Sort(arr, len); printf(排序后); Show(arr, len); }堆排序树1.二叉树首先是一棵树只不过任何节点的分支不能超过22.满二叉树简单来记就是这棵二叉树有多少层就把多少层摆满节点3.完全二叉树简单来记完全二叉树相较于满二叉树其最下面一层可以不用摆满但是如果要缺少节点的话也只能紧着最下面一层从右至左的少默认升序用大顶堆默认降序用小顶堆大顶堆首先是一颗完全二叉树并且父节点的值大于孩子节点的值小顶堆首先是一颗完全二叉树并且父节点的值小于孩子节点的值原始数据18 95 71 28 97 59 12 74 91 77如果知道父节点的下标怎么找到其两个孩子的下标1-3,4父推子2-5,63-7,8i-2i1,2i2如果知道孩子节点的下标怎么找到父节点的下标1-0子推父2-03-15-26-2i-(i-1)/2初始状态将一维数组arr得到将这个数组为臆想完全二叉树第一步将这颗完全二叉树调整为大顶堆第一次调整由内到外调整---从最后一个非叶子节点构成的子树开始调整由右向左由下到上所以根据定义可以得知我们第一次由内到外的调整调整子树的顺序为红-绿-橙-蓝-黑第二步将此时大顶堆的根节点最大值何其最后一个节点值进行交换然后再把最后一个节点断开连接有序了第三步只需要将头尾交换完成之后断开为节点然后重新调整为大顶堆即可只需要调整最外层框第四步重复执行二三两步直到大顶堆只剩一个节点为止单词调整函数如何实现函数传递的参数有哪些a.数组arr首元素地址b.数组arr有效节点c.要调整的子树的开始位置d.要调整的子树的结束位置1. 将此时要调整的子树的根节点的值拷贝一份给tmp(防止一会被覆盖)2. 找到当前空白格子然后判断其有无孩子如果有则进一步找到其较大的孩子然后将较大孩子的值和tmp的值进行比较3. 如果较大孩子的值大于tmp的值则向上顶(将此时较大孩子的值挪动到其父节点位置)4. 如果较大孩子的值向上顶则较大孩子位置会出现新的空白格子重复上面过程继续判断其是否有孩子如果有则继续找其较大孩子5. 如果较大孩子的值并不大于tmp的值则此时可以将tmp的值挪回去了6. 如果空白格子就没有孩子节点则认为触底了则此时也可以将tmp的值挪回去了7. tmp的值挪回去之后整体调整结束总结tmp拷贝的根节点的值什么时候可以放回去情况一如果空白格子没有孩子则触底可以将tmp放回去情况二如果空白格子有孩子但是其较大孩子的值并没有比tmp的值大则也可以将tmp放回去红黑树2.红黑树的性质性质一红黑树要求本体是一棵二叉搜索树口诀左根右性质二红黑树要求根节点和叶子节点都得是黑色根叶黑红黑树中把空节点NULL成为叶节点不是我们之前认为没有孩子的节点性质三红黑树要求红色节点的两个孩子都必须是黑色不红红性质四红黑树要求任意节点到其叶节点的所有路径上面的黑色结点的数目相同路黑同3.红黑树的核心平衡特性AVL树要求每一个节点的左右子树的高度差1红黑树平衡每一个节点的左右子树的高度差不超过2倍