文章目录
算法之排序篇介绍一、认识时间复杂度？
题目一：在一个数组中找到数组的最大值题目二：选择排序（时间：O(N^2) 空间：O(1))题目三：在一个已经排好序的数组中，找到目标值aim题目四：找到两个已经排好序的数组中的公有数字 二、认识空间复杂度？
题目一：实现数组的下列变换 三、经典排序算法的实现？
1、冒泡排序（稳定）2、插入排序（稳定）3、选择排序（不稳定）4、归并排序（稳定）
题目：返回数组对应位置前面所有比该位置小的和 5、快速排序（不稳定）
5.1简单将一个数组按照数组的最后一个数字将数组中的数字划分为小于等于该数放左边，大于该数放右边，该数放在两者之中5.2简单将一个数组按照数组的最后一个数字将数组中的数字划分为小于该数放左边，等于放在中间，大于该数放右边，该数放在两者之中5.3 快速排序实现思想5.4 快速排序中，时间复杂度和随机选择的数字有关5.5 题目：将奇数放在左边，偶数放在右边，空间复杂度O(1),并且保持奇数和偶数稳定 6、堆排序(堆结构太重要了）
6.1 堆排序的分类：
6.1.1 堆的建立6.1.2 堆排序需要的将0位置和最后一个交换后，0位置上的数往下降6.1.3 堆排序（依次到size=0） 7、在java中系统排序 四、对数器的实现
作用：对数器是用来干什么的呢？ 总结
一、认识时间复杂度？
时间复杂度为，一个算法流程中，常数操作数量的指标，这个指标叫做O,bigO,如果常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项系数之后，剩下的部分记为f(N),那么该算法的时间复杂度为O(f(N))
题目一：在一个数组中找到数组的最大值
在这个遍历的过程中，每次都取出数组中一个位置的数字和max比较，这个过程，取出数组的i位置的数据是1个常数操作，比较是另一个常数操作，所以每个位置的是两个常数操作，这个过程一共有N次，那么就是O(N）*2那么时间复杂度就是O(N)。
package exercise;
public class GetMaxElement {
public int getMaxElement(int[]arr)
{
if(arr==null) return Integer.MIN_VALUE;
int max=Integer.MIN_VALUE;
for (int i = 0; i max) max=arr[i];
}
return max;
}
}
题目二：选择排序（时间：O(N^2) 空间：O(1))
步骤：每次从后面的N个数中，选择最小的数字，放到前面
时间复杂度：每次从后面的N个数字中选出最小数的时间复杂度是O(N)，这样总的时间复杂度是O(N)+O(N-1)+O(N-2)+…O(1):这样求和是O(N^2)舍弃N的低次方和二次方前面的系数。
package ArrraySort;
public class SelectSort {
public void selectSort(int[]arr){
if(arr==null||arr.length<2) return;
// N-1次将后面数组的最小值放到数组前面
for (int i = 0; i
题目三：在一个已经排好序的数组中，找到目标值aim
步骤：用二分法查找，时间复杂度O(logN)
代码：
package exercise;
public class FindAimElement {
public int findAimElement(int[] arr,int aim,int L,int R){
if(L==R){
if(arr[L]==aim) return L;
return -1;
}
//如果中间这个是目标，那么返回目标下标
int mid=L+(R-L)/2;
if(arr[mid]==aim) return mid;
//循环递归寻找左边和右边的目标
int left=findAimElement(arr,aim,L,mid);
int right=findAimElement(arr,aim,mid+1,R);
//进行左右结果判断
return left!=-1?left:right!=-1?right:-1;
}
}
题目四：找到两个已经排好序的数组中的公有数字
方法一：暴力破解，在arr1数组中的每个数字都在arr2中进行遍历查找，时间复杂度是O(N*M)
代码：（优化：可以判断数字是否比后面的小，如果小，那么没有继续往后面比较的必要）
public ArrayDeque findSameWord1(int[] arr1, int[] arr2){
if(arr1==null||arr2==null||arr1.length<1||arr2.length<1) return null;
ArrayDeque result=new ArrayDeque<>();
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j
方法二：在arr1数组中的每个数字在arr2中进行二分查找，时间复杂度O(N*logM)
public ArrayDeque findSameWord2(int[] arr1, int[] arr2){
if(arr1==null||arr2==null||arr1.length<1||arr2.length<1) return null;
ArrayDeque result=new ArrayDeque<>();
FindAimElement findAimElement=new FindAimElement();
for (int i = 0; i < arr1.length; i++) {
//二分查找arr2数组中是否存在arr1数组元素
if(findAimElement.findAimElement(arr2,arr1[i],0,arr2.length-1)!=-1)
{
result.add(arr1[i]);
};
}
return result;
}
方法三：arr1数组和arr2数组两边交替查找数字，时间复杂度：O(N+M)
public ArrayDeque findSameWord3(int[] arr1, int[] arr2){
if(arr1==null||arr2==null||arr1.length<1||arr2.length<1) return null;
ArrayDeque result=new ArrayDeque<>();
int p=0;//p是arr1目前遍历的位置
int q=0;//q是arr2目前遍历的位置
while(p
方法 时间复杂度 方法一 O(N*M) 方法二 O(N*logM) 方法三 O(N+M）
方法二和三在不同的时候，都有可能会变得优秀
二、认识空间复杂度？
题目一：实现数组的下列变换
方法一：开辟额外数组空间，将后面的数据先放入数组，然后再放入前面的数，最后将额外数组空间的值拷贝回原数组空间：空间复杂度：O(N)
代码：
package exercise;
public class Array_leftAndright_Reverse {
public void messure1(int[] arr,int m){
if(arr==null||arr.length<1||m>arr.length-1||m<0) return ;
int[] arr1=new int[arr.length];
int index=0;
int p=m;
//进行原数组右边先拷贝到左边
while (p
方法二：先左右进行逆序，再整体逆序
public void messure2(int[] arr,int m){
if(arr==null||arr.length<1||m>arr.length-1||m<0) return ;
//先进行左边逆序
reverse(arr,0,m-1);
//再进行右边逆序
reverse(arr,m,arr.length-1);
//再进行整体逆序
reverse(arr,0,arr.length-1);
}
public void reverse(int[] arr,int L,int R){
while(L
三、经典排序算法的实现？
1、冒泡排序（稳定）
性能 指标 时间复杂度 O(n^2) 空间复杂度 O(1) 稳定性 稳定
代码实现：
package ArrraySort;
public class BubbleSort {
public void bubbleSort(int[] array){
if(array==null||array.length==0||array.length==1) return;
// 冒泡循环的次数n-1次
for (int i = array.length-1; i >0 ; i--) {
// 冒泡一次将最大的放到最后
for (int j = 0; j array[j+1]){
swap(array,j,j+1);
}
}
}
}
public void bubbleSort1(int[] array){
if(array==null||array.length==0||array.length==1) return;
for (int i = array.length-1; i >0 ; i--) {
// 判断有无进行交换
boolean work=false;
for (int j = 0; j array[j+1])
{
swap(array,j,j+1);
work=true;
}
}
if(!work){
break;
}
}
}
public void swap(int[] arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
2、插入排序（稳定）
性能 值 时间复杂度 O(n^2) 最好时间复杂度 O(n) 最坏时间复杂度 O(n^2) 空间复杂度 O(1) 稳定性 稳定
package ArrraySort;
public class InsertSort {
public void insertSort(int[] arr)
{
if(arr==null||arr.length==0||arr.length==1) return;
for (int i = 1; i 0&&arr[j]
3、选择排序（不稳定）
时间复杂度：O(N^2)
空间复杂度：O（1）
package ArrraySort;
public class SelectSort {
public void selectSort(int[]arr){
if(arr==null||arr.length<2) return;
// N-1次将后面数组的最小值放到数组前面
for (int i = 0; i
4、归并排序（稳定）
性能 值 时间复杂度 O(N*logN) 空间复杂度 O(N） 稳定性 稳定
归并排序时间复杂度可以达到O(1)，但是是论文级别的，内部缓存法
对于公式：
所以在归并排序中，算法时间复杂度是 O(N*logN)
代码：递归实现
package ArrraySort;
public class MergeSort {
public void mergeSort(int[]arr,int L,int R){
if(L==R) return;
int mid=L+(R-L)>>1;
mergeSort(arr,L,mid);
mergeSort(arr,mid+1,R);
processSort(arr,L,mid,R);
}
public void processSort(int[] arr,int L,int mid,int R){
// 数组长度
int length=R-L+1;
int i=0;
int l=L;
int r=mid+1;
int[] temp=new int[length];
while(l<=mid&&r<=R){
temp[i++]=arr[l]
代码：非递归实现
public void mergeSort2(int[]arr){
if(arr==null||arr.length<2)return;
//归并每一步的步长
int step=2;
//归并数组的大小小于数组的大小
while(step< arr.length){
//归并数组的起始
int L=0;
int R=L+step-1;
int mid=L+(R-L)/2;
while (R
题目：返回数组对应位置前面所有比该位置小的和
暴力破解法：时间复杂度O（N^2)
代码：
public int front_lessNumSum(int[]arr){
if(arr==null||arr.length<2) return 0;
int sum=0;
for (int i = 0; i
归并排序改良：
时间复杂度：O（N*logN)
public int mergeSolve(int[]arr){
return mergeSort(arr,0,arr.length-1);
}
public int mergeSort(int[]arr,int L,int R)
{
if(arr==null||arr.length<2) return 0;
if(L==R) return 0;
int mid=L+(R-L)/2;
int sum= mergeSort(arr,L,mid)+mergeSort(arr,mid+1,R)+solvePartition(arr,L,mid,R);
processSort(arr,L,mid,R);
return sum;
}
private int solvePartition(int[] arr, int l, int mid, int r) {
if(arr==null||arr.length<2) return 0;
//p是左边数组的下标
int p=l;
//q是右边数组的下标
int q=mid+1;
int sum=0;
while(q<=r){
while (p<=mid){
if(arr[p]
官方题解
public int mergeSolve2(int[]arr){
return mergeSort2(arr,0,arr.length-1);
}
private int mergeSort2(int[] arr, int L, int R) {
if(arr==null||arr.length<2) return 0;
if(L==R) return 0 ;
int mid=L+(R-L)/2;
return mergeSort2(arr,L,mid)+mergeSort2(arr,mid+1,R)+processSort2(arr,L,mid,R);
}
private int processSort2(int[] arr, int l, int mid, int r) {
if(arr==null) return 0;
int[] temp=new int[r-l+1];
int res=0;
int i=0;
int p=l;
int q=mid+1;
while (p<=mid&&q<=r){
res+=arr[p]
5、快速排序（不稳定）
性能 值 时间复杂度 O(N*logN) 空间复杂度 O(logN） 稳定性 不稳定
5.1简单将一个数组按照数组的最后一个数字将数组中的数字划分为小于等于该数放左边，大于该数放右边，该数放在两者之中
public void partition1(int[] arr,int L,int R)
{
if(arr==null||arr.length<2||L==R) return ;
//进行小于某个数的放在左边，大于的放在右边，等于的放在中间
int p=-1;
for (int i = 0; i
5.2简单将一个数组按照数组的最后一个数字将数组中的数字划分为小于该数放左边，等于放在中间，大于该数放右边，该数放在两者之中
public int[] partition2(int[] arr,int L,int R){
if(arr==null||arr.length<2) return null;
//保留下来划分数
int temp=arr[R];
int index=0;
int p=-1;
int q=R+1;
while(indextemp){
swap(arr,--q,index);
}else {
index++;
}
}
int[] result={p,q};
return result;
}
public void swap(int[]arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
5.3 快速排序实现思想
·······递归选择某个数，进行左右划分
package ArrraySort;
public class QucikSort {
public void quickSort(int[]arr,int L,int R){
if(arr==null||arr.length<2) return;
if(Ltemp){
swap(arr,--q,index);
}else {
index++;
}
}
int[] result={p,q};
return result;
}
public void swap(int[]arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
5.4 快速排序中，时间复杂度和随机选择的数字有关
最坏时间复杂度：如果刚刚好随机选择的数字都是最大的，或者最小的，那么其时间复杂度是0(N^2)
最好时间复杂度：若随机选择的数字刚刚好在中间，那么就是最好的情况，类似于归并排序，时间复杂度是0(NlogN)
长期期望时间复杂度：随机选择快速排序，均值为O(NlogN)
工程上最长使用：因为虽然它的最坏时间复杂度不好，但是它的常数项低，代码量少
5.5 题目：将奇数放在左边，偶数放在右边，空间复杂度O(1),并且保持奇数和偶数稳定
解题思路：快排的一次partition，但是快排是不稳定的，这道题相当于在问你快排怎么实现成稳定的版本，是论文级别的（0-1stableSort)
6、堆排序(堆结构太重要了）
性能 值 时间复杂度 O(N*logN) 空间复杂度 O(1）
堆结构是一颗完全二叉树
完全二叉树是什么？
二叉树是从左到右排序的，并且一层排满再到另一排
是：
不是：
将完全二叉树表示成数组形式：
第i个节点：
其左子元素是：2*i+1
右子元素：2*i+2
其父元素：(i-1)/2
6.1 堆排序的分类：
大根堆：每颗子树的父节点都大于这颗子树下面的所有结点
小根堆：每颗子树的父节点都小于这颗子树下面的所有结点
6.1.1 堆的建立
时间复杂度：
log1+log2+…+logN=O(N)
public void heapInsert(int[] arr,int index){
if(arr==null||arr.length<2||index>=arr.length||index<=0) return;
//计算父节点的位置
while (arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
6.1.2 堆排序需要的将0位置和最后一个交换后，0位置上的数往下降
public void heapify(int[]arr,int index,int heapSize){
if(arr==null||arr.length<2||index<0||index>=heapSize)return;
int left=index*2+1;
while (leftarr[left]?right:left;
if(arr[index]
6.1.3 堆排序（依次到size=0）
时间复杂度：O（N*logN)
工程上不经常用这个的原因：常数项太复杂，而且不稳定
package ArrraySort;
public class HeapSort {
public void heapSort(int[]arr){
if(arr==null||arr.length<2)return;
//首先进行堆排序
for (int i = 0; i 0){
heapify(arr,0,heapSize);
swap(arr,0,heapSize-1);
heapSize--;
}
}
public void heapInsert(int[] arr,int index){
if(arr==null||arr.length<2||index>=arr.length||index<=0) return;
//计算父节点的位置
while (arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
public void heapify(int[]arr,int index,int heapSize){
if(arr==null||arr.length<2||index<0||index>=heapSize)return;
int left=index*2+1;
while (leftarr[left]?right:left;
if(arr[index]
7、在java中系统排序
Arrays.sort(T[]arr);
size<=60:用插入排序
size>60:会先进行归并或者快排，将数组的大小缩小到60之后，然后用插入排序
那么选择用归并还是快排呢？取决于元素的类型：
若元素是int double char等基础类型，那么采用快排
若元素是对象，那么采用归并，这是因为稳定性的原因
四、对数器的实现
作用：对数器是用来干什么的呢？
简单来说，对数器就是用来验证我们写完代码的准确性的。
在工程中，我们总会实现时间复杂度和空间复杂度更低的代码，但是这些代码没办法保证一定准确，这时候我们就需要通过一定的随机测试数据来通绝对正确的方法和我们打出的方法进行对比，依次来验证我们打出代码的正确性
拿冒泡排序来举例子：
import ArrraySort.BubbleSort;
import ArrraySort.InsertSort;
import ArrraySort.MergeSort;
import ArrraySort.SelectSort;
import exercise.FindSameWord;
import org.junit.Test;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
public class testMachine {
//排序的对数器
@Test
public void selectTest(){
int times=50000;//比较的次数
int size=1000;//数组的可能长度
int value=10000;//数组的取值范围
for (int i = 0; i
总结
在上诉过程中，我们了解且实现了各种各样的排序算法，下面我们将接着学习
