排序算法:归并排序、快速排序

排序算法:归并排序、快速排序

 

相关博客:

排序算法:冒泡排序、插入排序、选择排序、希尔排序

排序算法:归并排序、快速排序

排序算法:桶排序、计数排序、基数排序

排序算法:堆排序

十大排序算法小结


一、归并排序:

1、工作原理:

归并排序的采用分治思想,如果要排序一个数组,我们先把数组从中间分成前后两个部分,然后对前后两个部分分别进行排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

2、动图演示:

排序算法:归并排序、快速排序

3、Java代码实现:

public class MergeSort {
	//归并排序:
	public void mergeSort(int[] a,int p,int r){
		//递归终止条件
		if(p>=r) return;
		
		int q=(p+r)/2;//取数组的中间点
		mergeSort(a,p,q);//对前半部分进行排序
		mergeSort(a,q+1,r);//对后半部分进行排序
		
		merge(a, p, q, r);//合并前后两个部分
	}
	
        //merge()函数是归并排序的重点
	public void merge(int[] a,int p,int q,int r){
		//初始化变量:i表示前半部分的下标,j表示后半部分的下标,k表示临时数组的下标
		int i=p;int j=q+1;int k=0;
		int[] tmp = new int[r-p+1];
		
		while(i<=q && j<=r){
			if(a[i]<=a[j]){
				tmp[k++]=a[i++];
			}else{
				tmp[k++]=a[j++];
			}
		}
		
		//将剩余数据拷贝到临时数组中
		for(;i<=q;i++) tmp[k++]=a[i];
		for(;j<=r;j++) tmp[k++]=a[j];
		
		//将tmp临时数组拷贝回原数组
		for(int x=0;x<r-p+1;x++) a[p+x]=tmp[x];
	}
}

4、算法分析:

(1)归并排序是一种稳定的排序算法;

(2)最好、最好、平均时间复杂度都是O(nlogn)。

(3)空间复杂度是O(n),所以不是原地排序。这也是归并排序的一个致命弱点。


二、快速排序:

1、工作原理:

快速排序也是利用分治思想。如果要排序一组数据,我们先选择这组数据中任意一个数据作为分区点pivot,然后遍历这组数据,将小于分区点pivot的放到左边,大于分区点pivot的放到右边,将pivot放到中间。然后再分别对左右两部分进行排序。

2、图片演示:

排序算法:归并排序、快速排序

3、Java代码实现:

public class QuickSort {

	public void quickSort(int[] a,int p,int r){
		//递归终止条件:
		if(p>=r) return;
		
		//获取分区点:
		int q=partition(a,p,r);
		quickSort(a,p,q-1);//对左分区进行排序
		quickSort(a,q+1,r);//对右分区进行排序
	}
	
	//返回分区点,快速排序的核心:
	public int partition(int[] a,int p,int r){
		
		int i=p;int pivot = a[r];
		for(int j=p;j<=r;j++){
			if(a[j]<pivot){
				swap(a,i,j);
				i++;
			}
		}
		swap(a, i, r);
		return i;
	}
	
	public void swap(int[] a,int x,int y){
		int temp=a[x];
		a[x]=a[y];
		a[y]=temp;
	}
}

其中,快速排序的核心就是paitition()分区函数,它的过程如下图所示:

排序算法:归并排序、快速排序

4、算法分析:

(1)快速排序是一种原地排序,空间复杂度为O(1)。

(2)快速排序是一种不稳定算法。

(3)快速排序是的最好时间复杂度、平均时间复杂度为O(nlogn)。但是在极端情况下,如果数组中的数据原来就是有序的,比如1,3,5,6,8,如果我们每次选择最后一个元素作为pivot,那每次分区得到的两个区间就是不均等的,我们需要大约进行n次分区操作,才能完成快排的整个过程,每次分区我们平均要扫描大约n/2个元素,这时时间复杂度为O(n^2),也就是最坏时间复杂度。


三、小结:归并与快排的区别:

(1)归并排序和快速排序都是用分治的思想,代码都是通过递归来实现的,但是归并排序的核心是merge()合并函数,而快速排序的核心是partition()分区函数。归并排序的处理过程是从下到上,先处理子问题,然后再合并。而快速排序的处理过程正好相反,它的处理过程是从上到下的,先分区,然后再处理子问题。这两种排序的处理过程如下图所示:

排序算法:归并排序、快速排序

(2)归并排序算法是一种任何情况下时间复杂度都比较稳定的排序算法,时间复杂度都是O(nlogn);快速排序算法最坏情况下时间复杂度为O(n^2),但是平均时间复杂度都是O(nlogn),不仅如此,快速排序时间复杂度退化到O(n^2)的概率非常小,我们可以通过合理选择pivot来避免这种情况。

(3)归并排序不是原地排序算法,空间复杂度比较高,为O(n);快速排序是原地排序算法,空间复杂度为O(1)。

(4)归并排序是稳定的算法,快速排序不稳定。

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114619.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • EnableEventValidation启用事件验证

    EnableEventValidation启用事件验证根据出错页面给出的提示消息可以知道,默认情况下是启用了事件验证的,在Aspx页HTML部分的Page指令处添加如下属性,就可以在页面回发时禁用事件验证<%@PageLanguage=”C#”EnableEventValidation=”false”.%>分析:出现这个错误一般是因为在客户端调用了js代码,改写了页面控件中的值,而通过postback再次requ…

  • 精进Quartz之路—Quartz备忘录

    官网: http://www.quartz-scheduler.org/Quartz任务调度快速入门 http://sishuok.com/forum/posts/list/405.html深入解读Quartz的原理 http://lavasoft.blog.51cto.com/62575/181907/Quartz2之入门示例 http://liuzidong.iteye.com/blog

  • Java实现MySQL数据库备份(一)

    Java实现MySQL数据库备份(一)Java实现MySQL数据库备份(一)

  • ue4在c盘的缓存_怎么清除ps在C盘的缓存

    ue4在c盘的缓存_怎么清除ps在C盘的缓存大家好,可能很多新手使用UE4的时候会发现C盘越来越小了,那是因为UE4引擎的缓存文件默认保存在C盘的缘故。下面来告诉大家怎么解决这个问题。概述一、出现的问题:UE4的缓存文件会导致C盘膨胀!二、解决的方式:请严格按照下列步骤来执行1.更改UE4的缓存路径2.删除UE4在C盘的缓存3.删除各个引擎版本SwarmAgent(联机构建)的缓存文件…

  • 4hutool源码分析:DateUtil(时间工具类)-格式化时间(万字长文源码分析,学大佬如何写代码)[通俗易懂]

    4hutool源码分析:DateUtil(时间工具类)-格式化时间(万字长文源码分析,学大佬如何写代码)[通俗易懂]知其然,知其所以然:4hutool源码分析:DateUtil(时间工具类)-格式化时间

    2022年10月29日
  • 语音合成综述

    语音合成综述title:语音合成综述tags:新建,模板,小书匠grammar_cjkRuby:true语音相关基础知识点:时域信号:一维原始信号傅里叶变换:得到频域特征短时傅里叶变换:傅里叶变换得到了频域信号,但是丢失了时域信号,所欲通过STFT得到时频信号梅尔频谱倒谱系数:单单频率信号表达不足,为了更加和人的耳朵听觉相符,我们使用了mel窗滤波,得到人耳的频率段幅度系数梅尔声谱…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号