- 1、快速排序
- 2、堆排序
- 3、二分查找
- 4、线性查找算法-BFPRT算法
- 5、广度优先搜索算法（BFS）
原理：该算法是分治法思想的一个应用，在数组中选这一个元素作为基准值，小于基准指的放到数组左边，大于基准值的放到数组右边，等于的随意放，然后在该基准值的左边区域在选择一个基准值，重复挑选步骤，在该基准值的右边也选择一个基准值，重复挑选步骤。最后子序列为长度为1的时候结束排序。
稳定性：不稳定
复杂度：时间复杂度O(nlogn)，空间复杂度O(nlogn)
算法描述：
假设有无序数组：[6,5,4,6,9,3,7,6,10,6,8]
第一轮循环：选择下标为0的值作为基准值，即arr[0]=6,小于等于6的放左边，大于6的放右边，循环后可得出数组[[5,4,6,3,6,6,6][9,7,10,8]]
第二次循环：分别对左右数组挑选基准值并拆分，左边基准值为arr[0]=5,右边基准值arr[7]=9,分别对左边和右边的子数组序列进行挑选，挑选后的结果为[[[4,3,5][6,6,6,6]][[7,8,9][10]]]
…
最后循环的结果即为排序后的结果。
代码实现：（代码千千万，这里只是其中一种）
public static void quickSort(int[] arr){
if(arr==null||arr.length<2){
return ;
}
long ctime=System.currentTimeMillis();
quickSplit(0,arr.length-1,arr);
System.out.println("耗时="+(System.currentTimeMillis()-ctime)+"ms");
}
private static void quickSplit(int start,int end,int[] arr){
if(start>=end){
return ;
}
int baseval=arr[start];
int idx=start+1;
for(int j=idx;j<=end;j++){
if(arr[j]
2、堆排序
堆的性质：堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
假设父节点下标为i，则该节点下左右子节点的下标分别为2i+1,2i+2.
原理：通过将给定数组构建成大根堆或者小根堆来进行排序，比如构建大根堆，保证根节点第一排序后是堆中最大的数，然后将根节点与最右侧的子节点交换位置，减掉最后一个左右节点，接着对剩余节点递归构建大根堆，重复构建和交换步骤，直到堆中剩余一个元素为止。
稳定性：不稳定
复杂度：时间复杂度O(nlongn)，空间复杂度O(1)
算法描述：
假设有无序数组：[5,3,6,4,7,8,2]
第一次构建大根堆后的数组为[8,7,5,4,3,6,2],将根节点与堆中最后一个节点交换得[2,7,5,4,3,6,8]，重新构建大根堆（此时最后一个节点已经被剪掉）。
第二次构建大根堆后的数组为[7,2,6,4,3,5,8]，将根节点与堆中最后一个节点交换得[5,6,2,4,3,7,8],重新构建大根堆（此时倒数第二个节点已经被剪掉）。
…
最后当堆中只剩一个元素的时候即是排序好的时候，排序结果如下[2,3,4,5,6,7,8]
代码实现：（代码千千万，这里只是其中一种）
private static void heapSort(int[] arr){
if(arr==null||arr.length<2){
return;
}
buildMaxHeap(arr.length,arr);
for(int i=arr.length-1;i>=0;i--){
swap(arr,0,i);
heapSwitch(i-1,i,arr);
}
}
private static void buildMaxHeap(int end,int[] arr){
heapSwitch(end,end,arr);
}
private static void heapSwitch(int i,int maxLen,int[] arr){
if(i<0){
return;
}
int left=2*i+1,right=2*i+2,large=i;
if(left
3、二分查找
原理：在给定的有序数组中，通过查找值与子数组序列的中间值比较来不断缩小查找范围，最终得出结果，找到就返回该值的索引，找不到返回-1.
复杂度：时间复杂度为O(log2n)
算法描述：
假设有序数组：[2,3,4,5,6,7,8,9],要查找的值为8。
第一次比较：mid=arr.length/2=4。Arr[mid]=6<8,则从右边区间缩小范围进行查找，此时需要查找的子数组序列为[7,8,9].
第二次比较：mid=(mid+end)/2=6,arr[6]=8==8,发现值匹配，返回下标6，查找结束。
因为每次都是折半查找，假设有n个元素，当前查找次数为i，则时间复杂度
t
(
n
)
=
i
+
t
(
n
/
2
(
i
−
1
)
)
t(n)=i+t(n/2^{(i-1)})
t(n)=i+t(n/2(i−1)),当
2
(
i
−
1
)
2^{(i-1)}
2(i−1)趋近于n的时候，
t
(
n
)
=
i
+
t
(
1
)
=
i
t(n)=i+t(1)=i
t(n)=i+t(1)=i,因为
2
(
i
−
1
)
=
n
2^(i-1)=n
2(i−1)=n，可得
i
=
l
o
g
2
n
+
1
i=log_2n+1
i=log2n+1,所以
t
(
n
)
=
l
o
g
2
n
+
1
t(n)=log_2n+1
t(n)=log2n+1，即
t
(
n
)
=
O
(
l
o
g
2
n
)
t(n)=O(log_2n)
t(n)=O(log2n)
算法实现：（算法千千万，这里只是其中一种）
private static int binarySearch(int[] sortedArr, int target) {
if (sortedArr == null || sortedArr.length == 0) {
return -1;
}
int mid = (sortedArr.length - 1) / 2;
int left = 0, right = sortedArr.length - 1;
while (left <= right) {
if (sortedArr[mid] == target) {
return mid;
}
if (sortedArr[mid] > target) {
right = mid - 1;
mid = (mid - 1 + left) / 2;
}
if (sortedArr[mid] < target) {
left = mid + 1;
mid = (mid + 1 + right) / 2;
}
}
return -1;
}
4、线性查找算法-BFPRT算法
BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。
算法描述：
- 将n个元素每5个一组，分成n/5(上界)组。
- 取出每一组的中位数，任意排序方法，比如插入排序。
- 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
- 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
- 若i==k，返回x；若i
k，在大于x的元素中递归查找第i-k小的元素。 终止条件：n=1时，返回的即是i小元素。 复杂度：BFPRT算法能够做到时间复杂度是 O(N)
算法实现：（算法千千万，这里只是其中一种）
private static int bfprtSearch(int start, int end, int[] arr, int k) {
if (k < 0 || arr.length == 1 || k > arr.length) {
return arr[0];
}
int p = getPivot(start, end, arr);
int idx = partition(start, end, arr, p);
if (idx == k) {
return arr[k];
} else if (k > idx) {
return bfprtSearch(idx + 1, end, arr, k);
} else {
return bfprtSearch(start, idx - 1, arr, k);
}
}
private static int getPivot(int start, int end, int[] arr) {
if (start == end) {
return arr[start];
}
int seg = (end - start) / 5;
int[] midArr = new int[seg + 1];
int cnt = 0, begin = -1;
for (int i = 0; i <= seg; i++) {
begin = start + i * 5;
if (i < seg) {
quickSplitForBfprt(begin, begin + 4, arr, begin+2);
midArr[cnt++] = arr[begin + 2];
} else {
quickSplitForBfprt(begin, end, arr, begin+2);
int ca = (begin + end) / 2;
midArr[cnt++] = arr[ca];
}
}
quickSplitForBfprt(0, midArr.length - 1, midArr, midArr.length / 2);
return midArr[midArr.length / 2];
}
private static int partition(int start, int end, int[] arr, int pivot) {
if (start == end) {
return start;
}
int mid = start, pIdx = -1;
//这里对整个区间进行遍历，小于等于pivot的都交换到左边，并记录最后一次和pivot值相等的交换后的下标位置
for (int j = start; j <= end; j++) {
if (arr[j] == pivot) {
pIdx = mid;
}
if (arr[j] <= pivot) {
swap(arr, mid, j);
mid++;
}
}
//根据上一步for循环记录的下标，将pivot交换到当前指针-1位置，保证pivot左边全都是小于等于pivot的，右边全都是大于pivot的
if (pIdx != -1) {
swap(arr, pIdx, mid - 1);
}
return mid - 1;
}
private static void quickSplitForBfprt(int start, int end, int[] arr, int mid) {
if (start >= end || start > mid) {
return;
}
int baseval = arr[start];
int idx = start + 1;
for (int j = idx; j <= end; j++) {
if (arr[j] < baseval) {
int tmp = arr[j];
arr[j] = arr[idx];
arr[idx] = tmp;
idx++;
}
}
int tm = arr[start];
arr[start] = arr[idx - 1];
arr[idx - 1] = tm;
quickSplitForBfprt(start, idx - 2, arr,(start+idx-2)/2);
quickSplitForBfprt(idx, end, arr,(idx+end)/2);
}
5、广度优先搜索算法（BFS）
原理：属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形： 1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。 4、如果遍历整个树还没有找到，结束程序。
最短路径查找
算法实现：（算法千千万，这里只是其中一种）
import java.util.linkedList;
import java.util.Queue;
public class BFSSearchMain {
//矩阵长度
private static int rectLength=10;
//记录当前元素是否已经访问过
private static int[][] visited=new int[rectLength][rectLength];
//下一步可能移动的方向
private static int[][] nextDirect=new int[][]{{-1,0},{0,1},{0,-1},{1,0}};
public static void main(String[] args){
int[][] rect=new int[][]{
{0,1,0,0,0,0,0,1,0,1},
{0,1,1,0,1,0,0,0,0,1},
{0,1,0,0,1,1,1,1,0,1},
{0,0,0,1,1,1,0,1,0,1},
{1,0,1,1,0,1,0,1,0,1},
{1,0,0,1,0,1,0,1,0,1},
{1,1,0,0,0,0,0,1,0,1},
{0,0,0,1,1,1,0,0,0,1},
{0,1,0,1,0,1,0,1,0,1},
{0,1,0,1,0,0,0,1,0,0},
};
System.out.println("最短步骤为:"+bfsSearch(rect));
}
private static int bfsSearch(int[][] rect){
Node head=new Node(0,0,0);
Queue queue= new linkedList<>();
queue.add(head);
while(!queue.isEmpty()){
Node n=queue.poll();
visited[n.x][n.y]=1;
for(int i=0;i<4;i++){
int x=n.x+nextDirect[i][0];
int y=n.y+nextDirect[i][1];
if(x==rectLength-1&&y==rectLength-1){
return n.step+1;
}
if(x>=0&&y>=0&&x 
