常见算法
算法：8种排序，二叉树，链表，图论，二分法，和诺发，排列组合，递归
时间复杂度：。。。。
1 排序
1.1 选择排序
图解：
选择排序
题目分析：
通过观察发现，本题目要实现把数组元素{13,46,22,65,3}进行排序
1.提到数组排序，就要进行元素值大小的比较，通过上图发现，我们想完成排序要经过若干次的比较才能够完成。
2.上图中用每圈要比较的第一个元素与该元素后面的数组元素依次比较到数组的最后一个元素，把小的值放在第一个数组元素中，数组循环一圈后，则把最小元素值互换到了第一个元素中。
3.数组再循环一圈后，把第二小的元素值互换到了第二个元素中。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。这种排序方式我们称为选择排序。
解题步骤：
1.使用for循环（外层循环），指定数组要循环的圈数（通过图解可知，数组循环的圈数为数组长度 - 1）
2.在每一圈中，通过for循环（内层循环）完成数组要比较的第一个元素与该元素后面的数组元素依次比较到数组的最后一个元素，把小的值放在第一个数组元素中
3.在每一圈中，要参与比较的第一个元素由第几圈循环来决定。如上图所示
a)进行第一圈元素比较时，要比较的第一个元素为数组第一个元素，即索引为0的元素
b)进行第二圈元素比较时，要比较的第一个元素为数组第二个元素，即索引为1的元素
c)依次类推，得出结论：进行第n圈元素比较时，要比较的第一个元素为数组第n个元素，即数组索引为n-1的元素
Java实现
/*
数组的排序：一般都是升序排序，元素从小到大排序
排序的方法：
选择排序
规则：
比较大小，位置交换
*/
public class HelloWorld{
public static void main(String[] args){
/*
定义方法，实现数组的选择排序
返回值：没有
排序对象：数组
实现步骤：
1.嵌套循环实现排序
外循环，控制的是一共比较多少次
内循环，控制的是每次比较了多少元素
2.判断元素的大小值
比较大小，交换位置
*/
int[] arr = new int[]{3,1,5,7,7,-9,0,2};
for(int i = 0;i < arr.length-1;i++){
//内循环，每次都在减少，修改变量的定义
for(int j = i+1; j < arr.length;j++){
if (arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
}
}
Python实现
list_num = [3,1,5,7,7,-9,0,2]
for i in range(len(list_num)-1):
for j in range(i+1,len(list_num)):
if list_num[i] > list_num[j]:
list_num[i],list_num[j] = list_num[j],list_num[i]
print(list_num)
1.2 冒泡排序
图解：
冒泡排序
题目分析：
通过观察发现，本题目要实现把数组元素{13,46,22,65,3}进行排序
1.提到数组排序，就要进行元素值大小的比较，通过上图发现，我们想完成排序要经过若干次的比较才能够完成。
2.上图中相邻的元素值依次比较，把大的值放后面的元素中，数组循环一圈后，则把最大元素值互换到了最后一个元素中。数组再循环一圈后，把第二大的元素值互换到了倒数第二个元素中。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。这种排序方式我们称为冒泡排序。
解题步骤：
1.使用for循环（外层循环），指定数组要循环的圈数（通过图解可知，数组循环的圈数为数组长度 - 1）
2.在每一圈中，通过for循环（内层循环）完成相邻的元素值依次比较，把大的值放后面的元素中
3.每圈内层循环的次数，由第几圈循环来决定。如上图所示
a)进行第一圈元素比较时，内层循环次数为数组长度 - 1
b)进行第二圈元素比较时，内层循环次数为数组长度 - 2
c)依次类推，得出结论：进行第n圈元素比较时，内层循环次数为数组长度 - n
Java实现
/*
数组的排序：一般都是升序排序，元素从小到大排序
排序的方法：
选择排序
规则：
比较大小，位置交换
*/
public class HelloWorld{
public static void main(String[] args){
/*
定义方法，实现数组的冒泡排序
返回值：没有
排序对象：数组
比较大小，交换位置
*/
int[] arr = new int[]{3,1,5,7,7,-9,0,2};
for(int i = 0;i < arr.length-1;i++){
//内循环的比较每次都是从0索引开始，且每次递减
for(int j = 0; j < arr.length-1-i;j++){
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
}
}
Python 实现
l = [13,46,22,65,3]
for i in range(len(l)-1):
for j in range(len(l)-1-i):
if l[j] > l[j+1]:
l[j],l[j+1] = l[j+1],l[j]
print(l)
1.3 数组逆序
数组逆序
题目分析：
通过观察发现，本题目要实现原数组元素倒序存放操作。即原数组存储元素为{11,22,33,44}，逆序后为原数组存储元素变为{44,33,22,11}。
1.通过图解发现，想完成数组元素逆序，其实就是把数组中索引为start与end的元素进行互换。
2.每次互换后，start索引位置后移，end索引位置前移，再进行互换
3.直到start位置超越了end位置，互换结束，此时，数组元素逆序完成。
解题步骤：
1.定义两个索引变量start值为0，变量end值为数组长度减去1（即数组最后一个元素索引）
2.使用循环，完成数组索引start位置元素与end位置元素值互换。
3.在循环换过程中，每次互换结束后，start位置后移1，end位置前移1
4.在循环换过程中，最先判断start位置是否超越了end位置，若已超越，则跳出循环
Java实现
public class HelloWorld{
public static void main(String[] args){
int[] arr = new int[]{1,3,4,5,6,7,9};
for(int start=0,end=arr.length-1;start < end;start++,end--){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
}
}
Python实现
list_num = [3,1,5,7,7,-9,0,2]
start = 0
end = len(list_num)-1
while start < end:
list_num[start],list_num[end] = list_num[end],list_num[start]
start += 1
end -= 1
print(list_num)
1.4. 快速排序（Quicksort）
快速排序(quick sort)采用了分治的策略。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
1.原理
1. 在数列之中，选择一个元素作为”基准”（pivot），或者叫比较值。
2. 数列中所有元素都和这个基准值进行比较，如果比基准值小就移到基准值的左边，如果比基准值大就移到基准值的右边
3.以基准值左右两边的子列作为新数列，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
举个例子，假设我现在有一个数列需要使用快排来排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我们来看看使用快排的详细步骤：
1. 选取中间的66作为基准值（基准值可以随便选）
2. 数列从第一个元素11开始和基准值66进行比较，小于基准值，那么将它放入左边的分区中，第二个元素99比基准值66大，把它放入右边的分区中。
3. 然后依次对左右两个分区进行再分区，直到最后只有一个元素
4. 分解完成再一层一层返回，返回规则是：左边分区+基准值+右边分区
Python实现
def quick_sort(list_num):
#当数组长度为1或者为空跳出递归
if len(list_num) <= 1:
return list_num
# 选取基准，随便选哪个都可以，选中间的便于理解
mid_num = list_num[len(list_num)//2]
# 定义基准值左右两个数列
left, right = [],[]
list_num.remove(mid_num)
for item in list_num:
#大于基准值的放右边
if item >= mid_num:
right.append(item)
#小于基准值的放左面
else:
left.append(mid_num)
#使用迭代进行比较
return quick_sort(left) + [mid_num] + quick_sort(right)
lst = [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
print(quick_sort(lst))
2 查找
2.1 二分法（折半查找）
图解:
二分法查找
题目分析：
通过观察发现，本题目要实现查找指定数值在元素有序的数组中存储的位置（索引），返回该位置（索引）。
1. 我们使用数组最中间位置的元素值与要查找的指定数值进行比较，若相等，返回中间元素值的索引
2. 最中间位置的元素值与要查找的指定数值进行比较，若不相等，则根据比较的结果，缩小查询范围为上次数组查询范围的一半；
再根据新的查询范围，更新最中间元素位置，然后使用中间元素值与要查找的指定数值进行比较
比较结果相等，返回中间元素值的索引
比较结果不相等，继续缩小查询范围为上次数组查询范围的一半，更新最中间元素位置，继续比较，依次类推。
3. 当查询范围缩小到小于0个元素时，则指定数值没有查询到，返回索引值-1。
解题步骤：
1. 定义3个用来记录索引值的变量，变量min记录当前范围最小索引值，初始值为0；变量max记录当前范围最大索引值，初始值为数组长度-1；变量mid记录当前当前范围最中间元素的索引值，初始值为(min+max) / 2
2. 使用循环，判断当前范围下，最中间元素值与指定查找的数值是否相等
若相等，结束循环，返回当前范围最中间元素的索引值mid
若不相等，根据比较结果，缩小查询范围为上一次查询范围的一般
中间元素值 比 要查询的数值大，说明要查询的数值在当前范围的最小索引位置与中间索引位置之间，此时，更新查询范围为:
范围最大索引值 = 上一次中间索引位置 -1；
中间元素值 比 要查询的数值小，说明要查询的数值在当前范围的最大索引位置与中间索引位置之间，此时，更新查询范围为:
范围最小索引值 = 上一次中间索引位置 +1；
在新的查询范围中，更新中间元素值的位置，再次使用最中间元素值与指定查找的数值是否相等。
中间索引值 = (范围最小索引值 +范围最大索引值) / 2;
3. 每次查询范围缩小一半后，使用if语句判断，查询范围是否小于0个元素，若小于0个元素，则说明指定数值没有查询到，返回索引值-1。
Java实现
public class HelloWorld{
public static void main(String[] args){
/*
定义方法，二分查找（折半查找）
返回值：没有
排序对象：数组
实现步骤：
1.需要定义三个变量
2.可以折半的条件 min <= max
3.被查找元素，和中间索引元素比较
元素 > 中间索引,小指针 = 中间+1
元素 < 中间索引,大指针 = 中间-1
元素 == 中间索引,找到了结束了
4.循环结束，无法折半
元素没有找到。返回-1
*/
//定义一个有序数组
int[] arr = new int[]{1,2,3,4,5,7,8,9};
//索引元素
int key = 5;
int min = 0;
int max = arr.length-1;
int mid = 0;
//循环折半条件
while(min <= max){
//公式，计算中间索引
mid = (min+max)/2;
if(arr[mid] > key){
max = mid-1;
}else if(arr[mid] <key){
min = mid+1;
}else{
System.out.println("找到了，索引为:"+mid);
break;
}
}
}
}
Python 实现
def func(list_num,index_num):
left = 0
right = len(list_num)-1
flag = False
while left <= right:
#公式，计算中间索引
mid = (left+right)//2
if index_num > list_num[mid]:
left = mid + 1
elif index_num < list_num[mid]:
right = mid -1
else:
print("找到了，索引为:%s"%mid)
flag = True
break
if not flag:
print("没有该元素")
lst = [1,2,3,4,5,7,8,9]
func(lst,11)
2.2. 哈希查找
待整理
2.3. 链表
待整理
2.4. 排列组合算法
待整理
2.5. 动态规划法
待整理
