Skip to content

Latest commit

 

History

History
192 lines (165 loc) · 12 KB

【排序】交换类排序—冒泡排序、快速排序手撕图解.md

File metadata and controls

192 lines (165 loc) · 12 KB
Raw

@TOC

前言

欢迎大家关注我的数据结构与算法专栏哈！，无论是日后面试还是笔试的，排序在数据结构与算法中有着举足轻重的地位，所以还是决定把数据结构这个专题好好写写，多研究研究！今天和大家一起学习交换类排序——冒泡和快排详解！ 在这里插入图片描述

在排序中，冒泡和快排是考察最多的了，当然在实行上面冒泡要相比快排简单很多。理解起来也算得上是最简单的排序算法，而快排的话很多面试笔试都是要求手撕的，所以重要性不言而喻！当然，对于排序算法我当初首次接触学习的时候只是萌萌懂懂的，只是大概了解，死记了模板，能将快排手写出来，刷题用。后来我发现我太傻吊了，，java中明明有Arrays.sort()这个api可以直接调用我为啥要憨呼呼的手写？多个条件排序重写下comparator接口就OK为啥还要憨呼呼的手写？。。。自此，就踏上了不手写快排的不归路。。。 在这里插入图片描述 后来，渐渐的，这个排序思想用的少，被我成功的遗忘。。现如今，被我重新拾起，深入理解下，防止哪一天又那个大佬让我手撕下不会就尴尬了哈哈，把学习过程分享给大家！

冒泡排序

介绍

冒泡排序，又称起泡排序。他是一种基于交换的排序典型，也是快排思想的基础。对于冒泡排序名字的由来，百度百科这么说：

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

在这里插入图片描述 当然，冒泡排序是一种稳定排序算法，时间复杂度为O(n^2^).基本思想是：从前往后把大元素往后调(或者从后向前把小元素往前调)。

分析

具体思想为(把大元素往后调)：

  • 从第一个元素开始往后跑，每到一个位置判断是否比后面的元素大，如果比后面元素大，那么就交换两者大小，然后继续向后，否则就直接向后前进，这样的话进行一轮之后就可以保证最大的那个数一直被交换交换到最末的位置可以确定。
  • 那么第二次同样从开始起向后判断着前进，如果当前位置比后面一个位置更大的那么就和他后面的那个数交换。但是有点注意的是，这次并不需要判断到最后，只需要判断到倒数第二个位置就行(因为第一次我们已经确定最大的在倒数第一，这次的目的是确定倒数第二)
  • 同理，后面的操作也是如此，直到第一个元素使得整个元素有序。

拿个例子来说，比如2，8，9，3，7，6，12，4这个序列的冒泡排序来说。会有多趟(7)排序，每一趟要执行多(8-k)次。 对于它的第一趟排序来说是这样的：

在这里插入图片描述 而多次排序每次的结果是这样的： 在这里插入图片描述 它的动态执行顺序为： 在这里插入图片描述

代码

在具体实现的时候，要分清是从小到大还是从大到小，还有次数也要注意，谨防越界！ 至于冒泡排序的关键代码为：

	private static void  maopaosort(int[] a) {
		// TODO Auto-generated method stub
		for(int i=a.length-1;i>=0;i--)
		{
			for(int j=0;j<i;j++)
			{
				if(a[j]>a[j+1])
				{
					int team=a[j];
					a[j]=a[j+1];
					a[j+1]=team;
				}
			}
		}
	}

快速排序

介绍

快速排序是对冒泡排序的一种改进，采用递归分治的方法进行求解。而快排相比冒泡是一种不稳定排序,时间复杂度最坏是O(n^2^),平均时间复杂度为O(nlogn),最好情况的时间复杂度为O(nlogn)。

分析

对于快排来说，基本思想是这样的

快排需要将序列变成两个部分，就是序列左边全部小于一个数，序列右面全部大于一个数，然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。

其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。但是通常我们取最左边的那个数。当然，为了实现这个目标，实现方式可能不一样，但是我这里采取的是大众常规的方式和方法。！ 在这里插入图片描述

这里的一个难题就是如何处理将比第一个数K小的全部放左面，把比K大的全部放右面！如果没有什么技巧，直接硬性往里面塞，你肯定要一个额外存储空间先把整个先存了。然后遍历比较然后放入目标区域。当然这样太浪费空间内存了。我们为了节省计算机资源，采取这样的方法：

  1. 先用一个空间标记这个最左侧的数K。然后先从右往左high--先找到一个比这个K小的数a[high]，把这个a[high]放到a[low]位置(因为这个a[low]的初始K已经被额外空间记录过，不用担心)。
  2. 这样右侧不符合要求小于K的已经调到最左侧了，我们再从左侧向右low++一直到a[low]>K.也就是找到第一个比K大的数，它在左侧不符合要求所以我们把它移动到右侧，而我们刚刚所说的a[high]已经被赋值移到左侧，所以我们把这个a[low]大于K的数值移动到右端a[high]处，这样又保证high右侧全部大于K，low左侧全部小于K。
  3. 就又开始重复第一步啦一直到low>high为止(即所有左侧都小于K，右侧都大于K)。

对于一个序列的2,8,3,7,6,9,4,12来说，它的执行过程图解大致是这样的： 1 . 首先2是最小的，采用递归分治时候左侧相当于为空，只需要把右侧再进行排序。 在这里插入图片描述 2 .对于右侧序列来说，先用K储存a[low]=8我们先从右侧找到第一个小与8的数字4。 在这里插入图片描述 3 .我们将它放到low位置替换，然后从low位置向右找到第一个大于k=8的再同样放到右侧。我们找到9，把9赋值给high位置。 在这里插入图片描述 4 .重复上面步骤直到high<low为止。我们最终将k这个值再次赋给这个位置的low。使得a[low]=k. 在这里插入图片描述 5 .就这样重复下去，直到整个序列有序即可！

代码

在书写代码的时候，要注意一些顺序，防止数组越界情况，可以写好debug一遍其实就很好理解了！当写代码遇到错误时候，不要急着就去找正确答案，能有时间自己发现错误，可以借助断点查看程序执行流程，这样对自己的收益是最大的！ 至于快排的代码，是这样的：

private static void quicksort(int [] a,int left,int right)
	{
		int low=left;
		int high=right;
	    //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
		if(low>high)//作为判断是否截止条件
			return;
		int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
		while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
		{
			while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
			{
				high--;
			}
			//这样就找到第一个比它小的了
			a[low]=a[high];//放到low位置
			while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置
			{
				low++;
			}
			a[high]=a[low];			
		}
		a[low]=k;//赋值然后左右递归分治求之
		quicksort(a, left, low-1);
		quicksort(a, low+1, right);		
	}

测试与总结

对于完整的代码，为

package 八大排序;

import java.util.Arrays;

public class 交换类排序 {
	
	public static void main(String[] args) {
		
		int a[]= {2,8,9,3,7,6,12,4};
		maopaosort(a);
		System.out.println(Arrays.toString(a));
		int b[]= {2,8,9,3,7,6,12,4};
		quicksort(b, 0, b.length-1);
		System.out.println(Arrays.toString(b));
	}

	private static void  maopaosort(int[] a) {
		// TODO Auto-generated method stub
		for(int i=a.length-1;i>=0;i--)
		{
			for(int j=0;j<i;j++)
			{
				if(a[j]>a[j+1])
				{
					int team=a[j];
					a[j]=a[j+1];
					a[j+1]=team;
				}
			}
		}
	}
	private static void quicksort(int [] a,int left,int right)
	{
		int low=left;
		int high=right;
	    //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
		if(low>high)
			return;
		int k=a[low];//取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
		while(low<high)
		{
			while(low<high&&a[high]>=k)
			{
				high--;
			}
			//这样就找到第一个比它小的了
			a[low]=a[high];
			while(low<high&&a[low]<=k)
			{
				low++;
			}
			a[high]=a[low];			
		}
		a[low]=k;
		quicksort(a, left, low-1);
		quicksort(a, low+1, right);		
	}
}

运行结果： 在这里插入图片描述

好了这个交换类排序就总结到这里了。总之，冒泡是很基础和容易，但是要注意这种简单排序所属的范畴(交换类)要和插入类等做好区分；而快排板子很好记，深入理解需要点时间消化吧。一次不行再来第二次，不行再来第三次，，再不行就放弃(手动滑稽)。。。

当然，如果感觉不错或者对你有所帮助，欢迎点赞收藏转发哈！如果感觉有问题或者纰漏还请指正哈！当然，笔者长期致力于<<数据结构与算法>>这个专栏的更新和维护，欢迎大家关注一波哈！

结语

原创不易，bigsai请你帮两件事帮忙一下:

  1. star支持一下， 您的肯定是我在平台创作的源源动力。

  2. 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

image-20201114211553660