1.插入排序
原理解释
举个简单的例子：
将10插入到已排序的数组arr中，保证数组元素从小到大排序
int arr[10]={3,7,8,9,12,15}; int key=10; for(int i=6-1;i>=0&&arr[i]>key;i--){ arr[i+1]=arr[i]; } arr[i]=key;将数组arr从后往前，从大到小遍历，i为索引
如果key＜arr[i]，那么将该索引对应的元素后移：arr[i+1]=arr[i],此时arr[i]为空，索引前移（i--）
不断循环该步骤，直到i<0（说明需要插到第一位arr[0]）或者直到arr[i]<=key,插入的位置就能找出，为索引i处，离开循环把key赋值给arr[i]
对乱序数组用插入排序
比如初始数组3 1 8 5 2 6 4
第一次循环：num[0]为有序，将num[1]赋值给key，根据上述方法将key插入有序数组中
1 3 8 5 2 6 4
第二次循环：num[0]、num[1]为有序，将num[2]赋值给key，根据上述方法将key插入有序数组中
1 3 8 5 2 6 4
第三次循环：num[0]、num[1]、num[2]为有序，将num[3]赋值给key，根据上述方法将key插入有序数组中
1 3 5 8 2 6 4
第四次循环：num[0]、num[1]、num[2]、num[3]为有序，将num[5]赋值给key，根据上述方法将key插入有序数组中
1 2 3 5 8 6 4
以此类推
可知第0次循环，第一个元素有序；第n-1次循环，n个元素都有序，故循环n-1次
代码实现
for(int i=1;i<n;i++){ //n为数组元素个数 int j; int key=num[i]; for(j=i-1;j>=0&&key<num[j];j--){ //j为索引 num[j+1]=num[j]; } num[j+1]=key; }2.不用任何字符串函数去除字符串里特定的字符
#include <stdio.h> #include <stdlib.h> int main() { char s[100]="ashifoa46278sdhaj"; int k=0; for(int i=0;s[i]!='\0';i++){ if(s[i]>='0'&&s[i]<='9'){ s[k++]=s[i]; } } s[k]='\0'; puts(s); return 0; }3.快速幂
概念引入
思考一个问题：7的10次方，怎样算比较快？
方法1：最朴素的想法，7*7=49，49*7=343，... 一步一步算，共进行了9次乘法。
这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。
方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。
但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。
方法3：先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。
模仿这样的过程，我们得到一个在 O(logn) 时间内计算出幂的算法，也就是快速幂
递归快速幂
思路
代码实现
#include <stdio.h> int qpow(int a, int n) { if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a; else { int temp = qpow(a, n / 2); return temp * temp; } } int main() { int a,n; scanf("%d %d",&a,&n); printf("%d",qpow(a,n)); return 0; }注意，函数中的temp变量是必要的，因为如果不把a^(2/n)记录下来，直接写成qpow(a, n /2)*qpow(a, n /2)，那会计算两次a^(2/n)，整个算法就退化为了 O(n)
非递归快速幂
在此之前我解释二个符号&（按位与）以及>>（位运算符）
n & 1：按位与
- 类型：位运算符
- 作用：判断
n的最低位是否为 1，即判断n是奇数还是偶数。 - 返回值：整数（0 或 1）
>>:右移位运算符
属于位运算符的一种它用于将一个整数的二进制表示向右移动指定的位数
result = value >> n;value：要被右移的整数（必须是整型：int,long,char等）n：右移的位数（非负整数）result：右移后的结果
1010>>=1，则1010变为了101
代码实现：
int qpow(int a,int n){ int res=1; while(n){ if(n&1){ res*=a; } n>>=1; a*=a; } return res; }
