• 

  博客主页(4条消息) 小吴_小吴有想法_CSDN博客-笔记,java,leetcode领域博主

• 

  欢迎关注

  

  点赞

  

  收藏和留言

  

• 

  天道酬勤，勤能补拙，和小吴一起加油吧 

• 

  17岁大一新生，水平有限，恳请各位大佬指点，不胜感激! 
• 🍊这里有一点路线小伙伴可以参考一下哈(4条消息) JAVA实现客户信息管理系统以及给大一寒假学生的建议_小吴-CSDN博客
• 参考书籍《算法4》，学习视频F1a;黑马程序员Java数据结构与算法黑马程序员Java数据结构与java算法，全网资料最全数据结构+算法教程，154张java数据结构图_哔哩哔哩_bilibili 尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

 

目录

冒泡排序(Bubble Sort )

图解 

代码实现 

@R_240_1304@分析

选择排序

图解

代码实现

 时间复杂度分析

插入排序

图解

代码实现

 时间复杂度分析

希尔排序

图解

代码实现

 时间复杂度的探讨笔记

归并排序

 图解

代码实现

 时间复杂度分析

快速排序

图解

代码实现

 时间复杂度分析

基数排序

图解 

​

代码实现

 时间复杂度分析

---

冒泡排序(Bubble Sort )

排序前：{3,4,5,6,7,2,1}

排序后：{1,2,3,4,5,6,7}

图解 

原理：

•  比较相邻的元素，如果前一个元素比后一个元素大，就交换这两个元素的位置
• 对每一对相邻的元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值

代码实现 

public static void main(String[] args)
{
	int t=0;
	int[] a= {3,4,5,6,7,2,1};
	for(int i=0;i<a.length-1;i++)
	{
		for(int j=0;j<a.length-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	for(int i=0;i<a.length;i++)
	{
		System.out.PRint(a[i]+"  ");
	}	
}

时间复杂度分析

分析内循环体的执行次数，在最坏的情况下，也就是加入要排序的元素为{7,6,5,4,3,2,1}逆序，那么：

• 元素的比较次数为：(N-1)+(N-2)+(N-3)+...+2+1=N^2/2-N/2;
• 元素的交换次数为：(N-1)+(N-2)+(N-3)+...+2+1=N^2/2-N/2;
• 总执行次数为：N^2-N;
• 故时间复杂度为O(N^2);

选择排序

排序前：{4,6,8,7,9,2,10,1}

排序后：{1,2,4,6,7,8,9,10}

图解

原理：

• 每一次遍历过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后可以找到最小值所在的索引
• 交换第一个索引处和最小值所在索引处的值

代码实现

import java.util.Arrays;
public class test{
	//对数组a中的元素进行排序
	public static void sort(Comparable [] a)
	{
		for(int i=0;i<a.length-1;i++)
		{
			int min=i;//定义一个变量，记录最小元素所在位置的索引，默认为参与选择排序的第一个元素所在的位置
			for(int j=i+1;j<a.length;j++)//从已经选择出来了的数后面开始挑选
			{
				if(greater(a[min],a[j]))//需要比较最小元素索引min处的值和j索引处的值
				{
					min=j;
				}
				exch(a,i,min);
				}
			}
		}
	private static boolean greater(Comparable a,Comparable b)//比较a元素是否大于b元素
	{
		return a.COMpareTo(b)>0;
	}
	private static void exch(Comparable[] a,int i,int j)//数组元素i和j交换位置
	{

		Comparable t;
		t=a[i];
		a[i]=a[j];
		a[j]=t; 
	}
	
public static void main(String[] args)
{
	Integer []a= {4,6,8,7,9,2,10,1};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 时间复杂度分析

元素的比较次数为：(N-1)+(N-2)+(N-3)+...+2+1=N^2/2-N/2;       

数据的交换次数为：N-1（最外层的for循环执行几次，就发生几次交换）；

总执行次数：N^2/2+N/2-1；

时间复杂度：O(N^2);

插入排序

排序前：{4,3,2,10,12,1,5,7}

排序后：{1,2,3,4,5,7,10,12}

图解

 原理：

• 把所有的元素分为两组，已经排序的和未排序的
• 找到未排序组中的第一个元素，向已经排序的组中插入
• 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位

代码实现

import java.util.Arrays;
public class test{
	//对数组a中的元素进行排序
	public static void sort(Comparable [] a)
	{
		for(int i=1;i<a.length;i++)
		{
	
			for(int j=i;j>0;j--)//比较索引j处的值和j-1处的值，如果索引j-1处的值比索引j处的值大，则交换数据
				//如果不大的话，退出循环即可
			{
				if(greater(a[j-1],a[j]))
				{
					exch(a,j-1,j);
				}else
					break;
			}
		}
	}
	private static boolean greater(Comparable a,Comparable b)//比较a元素是否大于b元素
	{
		return a.compareTo(b)>0;
	}
	private static void exch(Comparable[] a,int i,int j)//数组元素i和j交换位置
	{

		Comparable t;
		t=a[i];
		a[i]=a[j];
		a[j]=t; 
	}
	
public static void main(String[] args)
{
	Integer []a= {4,6,8,7,9,2,10,1};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 

 时间复杂度分析

分析内循环体的执行次数，在最坏的情况下，也就是待排序的元素为{12,10,7,5,4,3,2,1}，那么：

• 比较次数为：(N-1)+(N-2)+(N-3)+...+2+1=N^2/2-N/2;     
• 交换次数为：(N-1)+(N-2)+(N-3)+...+2+1=N^2/2-N/2;      
• 总执行次数：N^2-N;
• 故时间复杂度为：O(N^2);

希尔排序

《算法4》：

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要讲它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序数组创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够进行数组排序。这就是希尔排序

 排序前：{9,1,2,5,7,4,8,6,3,4}

 排序后：{1,2,3,4,4,5,6,7,8,9}

图解

 原理：

1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2. 对分好组的每一组数据完成插入排序；
3. 减小增长量，最小减为1，重复第二部步操作

代码实现

import java.util.Arrays;
public class test{
	//对数组a中的元素进行排序
	public static void sort(Comparable [] a)
	{
		int N=a.length;
		int h=1;
		//确定增长量h的最大值
		while(h<N/2)
		{
			h=h*2+1;
		}
		while(h>=1)//当增长量h小于1，排序结束	 
		{
			//1.找到待插入的元素
			for(int i=h;i<N;i++)
			{
		//2.将待插入的元素插入到有序数组中
			for(int j=i;j>=h;j-=h)
			{  //待插入的元素是a[j],比较a[j]和它前面的a[j-h]
				if(greater(a[j-h],a[j]))//如果a[j-h]大，交换元素
				{
					exch(a,j-h,j);//因为前面都插入排序好了，只需要比较a[j]前面的那个a[j-h]即可咯
				}
				else
				{
					break;//说明待插入元素已经找到了合适的位置，结束循环
				}
			}
			}

		h=h/2;//减小h的值
	}
	}
	private static boolean greater(Comparable a,Comparable b)//比较a元素是否大于b元素
	{
		return a.compareTo(b)>0;
	}
	private static void exch(Comparable[] a,int i,int j)//数组元素i和j交换位置
	{

		Comparable t;
		t=a[i];
		a[i]=a[j];
		a[j]=t; 
	}
	
public static void main(String[] args)
{
	Integer []a= {9,1,2,5,7,4,8,6,3,4};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 时间复杂度的探讨笔记

希尔排序中增长量h并没有固定的规则，研究希尔排序性能需要的数学论证也超出了我使用的《算法4》这本书的范围，对于中等大小的数组它的运行时间是可以接受的。它的代码量很小，且不需要使用额外的内存空间。如果需要解决一个排序问题而又没有系统排序函数可用，可用先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。

归并排序

递归排序算法：归并排序。要将一个数组排序，可以先(递归地)将它分成两半分别排序，然后将结果归并起来。归并排序能够保证将任意长度为N的数组排序所需时间和NLOGN成正比；它的主要缺点则是它所需的额外空间和N成正比。

排序前：{7,4,5,8,1,3,6,2}

排序后：{1,2,3,4,5,6,7,8}

 图解

 原理：

1. 尽可能一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数都是1为止
2. 将相邻的两个子组进行合并成一个有序的大组
3. 不断的重复步骤2，直到最终只有一个组为止

代码实现

import java.util.Arrays;
public class test{
	//归并所需要的辅助数组
	private static Comparable[] assist;
	//对数组a中的元素进行排序
	public static void sort(Comparable [] a)
	{
		//1.初始化辅助数组assist
		assist=new Comparable[a.length];
		//2.定义一个lo变量和一个hi变量，分别记录数组中的最小索引和最大索引
		int lo=0;
		int hi=a.length-1;
		//3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
		sort(a,lo,hi);		
	}
	public static void merge(Comparable[] a,int lo,int mid,int hi)
	{
		//定义三个指针
		int i=lo;
		int p1=lo;
		int p2=;mid+1;
		//遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组对应索引位置
		while(p1<=mid&&p2<=hi)
		{//比较对应索引处的值
			if(greater(a[p1],a[p2]))
			{
			 assist[i++]=a[p1++];
			}else
			{
				assist[i++]=a[p2++];
			}
		}
		//遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
		while(p1<=mid)
		{
			assist[i++]=a[p1++];
		}
		//遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
		while(p2<=hi)
		{
			assist[i++]=a[p2++];
		}
		//把辅助数组中的元素拷贝到原数组中
		for(int m=lo;m<=hi;m++)
		{
			a[m]=assist[m];
		}
	}
	public static void sort(Comparable[] a,int lo,int hi)
	{
		if(hi<=lo)
		{
			return;//安全检验
		}
		//从lo到hi之间的数据分为2个数组
		int mid=lo+(hi-lo)/2;
		//分别对每一组数据进行排序
		sort(a,lo,mid);
		sort(a,mid+1,hi);
		//再把两个数组进行归并
		merge(a,lo,mid,hi);	//递归，分而治之，当递归到只有一个元素的时候，终止递归
	}
	private static boolean greater(Comparable a,Comparable b)//比较a元素是否大于b元素
	{
		return a.compareTo(b)<0;
	}
	private static void exch(Comparable[] a,int i,int j)//数组元素i和j交换位置
	{

		Comparable t;
		t=a[i];
		a[i]=a[j];
		a[j]=t; 
	}
	
public static void main(String[] args)
{
	Integer []a= {7, 4, 5, 8, 1, 3, 6, 2};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 时间复杂度分析

设数据规模大小为N，运行时间为T(N),当把N分为两半，则处理大小为N/2的子数组花费时间为T(N/2),合并花费时间与数据规模成正比:N，所以T(N)=2*T(N/2)+N

最终得时间复杂度为O(NlogN）

快速排序

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然you

排序前：{6,1,2,7,9,3,4,5,8}

排序后：{1,2,3,4,5,6,7,8,9}

图解

原理：

1. 首先设定一个分界值，通过分界值将数组分成左右两部分
2. 将大于或等于分界值的数据放到数组的右边，小于分界值的数据放到数组的左边，此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值
3. 然后，左边和右边的数据可以独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排序好后，再递归排好右侧部分的顺序，当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了

 

代码实现

import java.util.Arrays;
public class test{
	//对数组a中的元素进行排序
	public static void sort(Comparable [] a)
	{
		//定义一个lo变量和一个hi变量，分别记录数组中的最小索引和最大索引
		int lo=0;
		int hi=a.length-1;
		//调用sort方法完成数组a中,从索引lo到索引hi的元素的排序
		sort(a,lo,hi);		
	}
	//对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
	public static int partITion(Comparable[] a,int lo,int hi)
	{
		//确定分界值
		Comparable key=a[lo];
		//定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置	
		int left=lo;
		int right=hi+1;
		
		//切分
		while(true) {
			//先从右往左扫描，移动rigth指针，找到一个比分界值小的元素，停止
			while(greater(key,a[--right]))
			{
				if(right==lo)//右指针扫描到最左边了
				{
					break;
				}			
			}
			//再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
			while(greater(a[++left],key))
			{
				if(left==hi)//扫描到最右边了
				{
					break;
				}	
			}
			//判断left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
			  if(left>=right)//扫描完毕，结束扫描
				  {
				  break;
				  }else
				  {
					  exch(a,left,right);
				  }
			  }	
			exch(a,lo,right);//	
		return right;
	}
	//对数组a中从索引lo到索引hi之间的元素进行排序
	public static void sort(Comparable[] a,int lo,int hi)
	{
		if(hi<=lo)
		{
			return ;
		}
		//需要对数组中lo索引到hi索引处的元素进行分组(左子组和右子组)
		 int partition=partition(a,lo,hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引
		//让左子组有序
		sort(a,lo,partition-1);//结束索引为分界值前一个索引
		//让右子组有序
		sort(a,partition+1,hi);//起始索引为分界值后一个索引
	}
	private static boolean greater(Comparable a,Comparable b)//比较a元素是否大于b元素
	{
		return a.compareTo(b)<0;
	}
	private static void exch(Comparable[] a,int i,int j)//数组元素i和j交换位置
	{

		Comparable t;
		t=a[i];
		a[i]=a[j];
		a[j]=t; 
	}
	
public static void main(String[] args)
{
	Integer []a= {6,1,2,7,9,3,4,5,8};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 时间复杂度分析

快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(N),但整个快速排序的时间复杂度和切分的次数相关

最优情况:每一次切分选择的基本数字刚好将当前序列等分，时间复杂度为O(NlogN)

最坏情况：每一次切分选择的基准数字是当前序列中的最大数或最小数，这使得每一次切分都会有一个子组，那么总共就得切分N次,所以最坏情况下时间复杂度是O(N^2)

平均情况下的时间复杂度：O(NlogN)

基数排序

通过键值的各个位的值，将要排序的元素分配至某些桶中，达到排序的作用。

基数排序是效率高的稳定性排序算法，是桶排序的扩展。

图解 

 

代码实现

这时1,2,3轮分开写的情况，我们可以发现规律，第一轮是a[i]/1%10,第二轮是a[i]/10%10，第三轮是a[i]/100%10

import java.util.Arrays;
public class test{
	//对数组a中的元素进行排序
	//第一轮处理个位
	public static void sort(int [] a)
	{
		//定义一个二维数组，每个桶就是一个一维数组
	int [][] arr= new int [10][a.length];//为了防止放置数据的时候数据溢出，用a.length。前面那个10代表0——9,10个一位数组
		//记录每个桶中实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
		int [] b=new int[10];//记录10个桶
		//第一步(针对元素的个位数进行处理)
		for(int i=0;i<a.length;i++)
		{
		int n=a[i]%10;
		//放入到对应的桶中
		arr[n][b[n]]=a[i];
		b[n]++;//代表这个桶里的数据增加了
		}
		 //按照这个桶的顺序(一维数组的下标以此取出数据，放入原来数组)
		int index=0;
		//遍历每一桶,并将桶中的数据放入到原数组
		for(int j=0;j<b.length;j++)
		{
		//如果桶中有数据
		if(b[j]!=0)//循环该桶,即下标为j的一维数组
		{
			for(int m=0;m<b[j];m++)
			{
				a[index++]=arr[j][m];
			}
			
		}
		//第一轮处理后，需要将原来代表桶里的数据个数的值清0,否则会影响下一轮
				b[j]=0;
		}
		
  
    //第二轮，处理十位数
			for(int i=0;i<a.length;i++)
			{
			int n=a[i]/10%10;
			//放入到对应的桶中
			arr[n][b[n]]=a[i];
			b[n]++;//代表这个桶里的数据增加了
			}
			 //按照这个桶的顺序(一维数组的下标以此取出数据，放入原来数组)
			index=0;
			//遍历每一桶,并将桶中的数据放入到原数组
			for(int j=0;j<b.length;j++)
			{
			//如果桶中有数据
			if(b[j]!=0)//循环该桶,即下标为j的一维数组
			{
				for(int m=0;m<b[j];m++)
				{
					a[index++]=arr[j][m];
				}
				
			}
			b[j]=0;
			}
			//第三轮，处理百位数
			for(int i=0;i<a.length;i++)
			{
			int n=a[i]/100%10;
			//放入到对应的桶中
			arr[n][b[n]]=a[i];
			b[n]++;//代表这个桶里的数据增加了
			}
			 //按照这个桶的顺序(一维数组的下标以此取出数据，放入原来数组)
			index=0;
			//遍历每一桶,并将桶中的数据放入到原数组
			for(int j=0;j<b.length;j++)
			{
			//如果桶中有数据
			if(b[j]!=0)//循环该桶,即下标为j的一维数组
			{
				for(int m=0;m<b[j];m++)
				{
					a[index++]=arr[j][m];
				}
				
			}
		
			}
	   } 
public static void main(String[] args)
{
	int []a= {53,3,542,748,14,214};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 所以通过以上的展示我们可以总结规律去处理，找出数组中的最大值的位数去处理

最终代码，可以先理解上一段代码再得出结论，总结，处理起来就方便多了

import java.util.Arrays;
public class test{
	//对数组a中的元素进行排序
	//第一轮处理个位
	public static void sort(int [] a)
	{
		//找出最大数的位数
			int max=a[0];
			for(int i=0;i<a.length;i++)
			{
				if(a[i]>max)
				{
					max=a[i];
				}
			}
			int maxlength =(max+"").length();
		//定义一个二维数组，每个桶就是一个一维数组
	int [][] arr= new int [10][a.length];//为了防止放置数据的时候数据溢出，用a.length。前面那个10代表0——9,10个一位数组
		//记录每个桶中实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
		int [] b=new int[10];//记录10个桶
		
		for(int c=0,f=1;c<maxlength;c++,f*=10)
		{   
			//针对每个元素对应的位进行排序，第一次是个位，第二次是十位，第三次是百位  
			for(int i=0;i<a.length;i++)
			{
				//取出每个元素对应位的数
			int n=a[i]/f%10;
			//放入到对应的桶中
			arr[n][b[n]]=a[i];
			b[n]++;//代表这个桶里的数据增加了
			}
			 //按照这个桶的顺序(一维数组的下标以此取出数据，放入原来数组)
			int index=0;
			//遍历每一桶,并将桶中的数据放入到原数组
			for(int j=0;j<b.length;j++)
			{
			//如果桶中有数据
			if(b[j]!=0)//循环该桶,即下标为j的一维数组
			{
				for(int m=0;m<b[j];m++)
				{
					a[index++]=arr[j][m];
				}
				
			}
			//第一轮处理后，需要将原来代表桶里的数据个数的值清0,否则会影响下一轮
					b[j]=0;
			}
			System.out.println("第"+(c+1)+"轮，排序处理的结果为"+Arrays.toString(a));
		}
		
	}

public static void main(String[] args)
{
	int []a= {53,3,542,748,14,214};
	test.sort(a);
	System.out.print(Arrays.toString(a));
}
}

 时间复杂度分析

基数排序会耗费额外的内存空间，当数据过多时，可能出现OutOfMemoryError

如果有负数的数组，最好不用基数排序

平均时间复杂度：O(n*k)  空间复杂度O(n+k)

 

学习如逆水行舟，不进则退。和小吴一起加油吧！