排序算法

(1)冒泡排序
(2)快速排序参考博客(快排原理)
参考博客(形象化过程)
快排原理:
在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。
整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。
一趟排序的方法:
1,定义i=0,j=A.lenght-1,i为第一个数的下标,j为最后一个数下标
2,从数组的最后一个数Aj从右往左找,找到第一小于key的数,记为Aj;
3,从数组的第一个数Ai 从左往右找,找到第一个大于key的数,记为Ai;
4,交换Ai 和Aj
5,重复这个过程,直到 i=j
6,调整key的位置,把A[i] 和key交换
假设要排的数组为:A[8] ={ 5 2 8 9 2 3 4 9 }
选择 key = 5, 开始时 i=0,j=7
index 0 1 2 3 4 5 6 7

开始: 5 2 8 9 2 3 4 9
i j
第一次找 5 2 8 9 2 3 4 9
i j
交换: 5 2 4 9 2 3 8 9
i j
第二次找 5 2 4 9 2 3 8 9
i j
交换: 5 2 4 3 2 9 8 9
i j
第三次找 5 2 4 3 2 9 8 9
ij
调整key: 2 5 4 3 5 9 8 9
ij
(3)插入排序参考博客
将一个记录插入到已经排好的有序表中,从而得到一个新的、记录数增1的有序表。一个非常形象的例子就是将新摸到的一张扑克牌,经过比较后,将它插入排好序的扑克里面,如下图所示。
当最好的情况,也就是要排序的表本身就是有序的,此时只有数据比较,没有数据移动,时间复杂度为O(n)。
当最坏的情况,即待排序的表是逆序的情况,此时需要比较次数为:2+3+…+n=(n+2)(n-1)/2 次,而记录移动的最大值也达到了 (n+4)(n-1)/2 次,复杂度为O(n^2)
在这里插入图片描述
从数组的第二个元素开始,取得当前待处理的元素,插入到当前元素之前的子数组里面,直到数组的末尾。
在这里插入图片描述
**(4)**希尔排序及其参考博客
希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。
希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,小的基本在前,大的基本在后。然后缩小增量,到增量为1时,其实多数情况下只需微调即可,不会涉及过多的数据移动。
希尔排序
**(5)**归并排序及其参考博客
归并排序
**(6)**基数排序之数组实现 基数排序之队列实现

package testSort;

import java.util.Arrays;

public class Sort {
	public static void main(String args[]) {
		int[] array=new int[] {1,3,5,7,9,2,4,6,8,10};
		System.out.println("排序前:"+Arrays.toString(array));
//		bubbleSort(array); 
//		insertSort(array);
//		quickSort(array,0,5);
//		shellSort(array);
//		radixSort(array);
//		radixQueueSort(array);
        mergeSort(array,0,array.length-1);
		System.out.println("排序后:"+Arrays.toString(array));	
	}
	
//冒泡排序法==========================================================================
	public static void bubbleSort(int[] a) {
		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]) {
					int t=a[j+1];
					a[j+1]=a[j];
					a[j]=t;
				}
			}
		}
	}
//快速排序法==========================================================================
	public static void quickSort(int[] a,int low,int high) {
		if(low>=high) {
			return;
			}
			//{1,4,7,2,5,8,-4,-12} 
			int i=low;//初始下标
			int j=high;
			//key
			int key=a[i];
			while(i<j) {
				//先从后面进行排序
				while(a[j]>=key&&i<j) {
					j--;
				}
				if(i<j) {
					int t=0;
					t=a[j];
					a[j]=a[i];
					a[i]=t;
				}
				
				while(a[i]<=key&&i<j) {
					i++;
				}
				if(i<j) {
					int t=0;
					t=a[i];
					a[i]=a[j];
					a[j]=t;
				}
			}
			//对于基准左侧集合重复操作
			quickSort(a,low,i-1);
			//对于基准右侧集合操作
			quickSort(a,i+1,high);
		
	}
	
//插入排序法==============================================================================
	public static void insertSort(int[] a) {
		int i,j,insertData;//要插入的数据
		for(i=1;i<a.length;i++) {// 从数组的第二个元素开始循环将数组中的元素插入
			insertData=a[i];//设置数组中的第2个元素为第一次循环要插入的数据
			j=i-1;//每一次与前一个数字相比
			while(j>=0&&insertData<a[j]) {
				a[j+1]=a[j];//如果要插入的元素小于第j个元素,就将第j个元素向后移动
				j--;
			}
			a[j+1]=insertData;// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
		}	
	}
	
//希尔排序====================================================================================
	public static void shellSort(int[] a) {
		for(int gap=4;gap>0;gap/=2) {//a.length/gap=分的组数
			for(int i=gap;i<a.length;i++) {
				for(int j=i;j>gap-1;j-=gap) {//插入排序的原理 跳跃间隔的元素相比较
					if(a[j]<a[j-gap]) {
						swap(a,j,j-gap);
					}
				}
			}
		}
		
	}
	static void swap(int[] arr,int i,int j) {
		int t=arr[i];
		arr[i]=arr[j];
		arr[j]=t;
		
	}
//归并排序===============================================================================
	public static void mergeSort(int[] a,int low,int high) {
		int middle=(high+low)/2;
		if(low<high) {
			mergeSort(a,low,middle);//递归操作,调用自己,处理左边
			mergeSort(a,middle+1,high);//处理右边
			sort(a,low,middle,high);//进行归并操作
		}
		
	}
	public static void sort(int[] a,int low,int middle,int high) {
		//用于存储归并后的临时数组
		int[] temp=new int[high-low+1];
		//记录第一个数组中需要遍历的下标
		int i=low;
		//记录第二个数组中需要遍历的下标
		int j=middle+1;
		//用于记录在临时数组中存放的下标
		int index=0;
		//遍历两个数组的数字 放入临时数组中
		while(i<=middle&&j<=high) {//漏掉等于号导致出错
			if(a[i]<=a[j]) {
				//把小的放入临时数组中
				temp[index]=a[i];
				//让下标后移一位
				i++;			
			}else {
				temp[index]=a[j];
				j++;
			}
			index++;
		}
		//处理多余的数据
		while(j<=high) {
			temp[index]=a[j];
			j++;
			index++;
		}
		while(i<=middle) {
			temp[index]=a[i];
			i++;
			index++;
		}
		//把临时数组放置原数组
		for(int k=0;k<temp.length;k++) {
			a[k+low]=temp[k];
		}
	}
//基数排序=====================================================================================

	public static void radixSort(int[] a) {
		//找到最大的数字
		int max=Integer.MIN_VALUE;
		for(int i=0;i<a.length;i++) {
			if(a[i]>max) {
				max=a[i];
			}
		}
/*补充:
Integer类中的一个int类型的常量MAX_VALUE;它代表int所能表示的最大值 0x7FFFFFFF(0111 1111 1111 1111 1111 1111 1111 1111)
Integer类中的另一个常量MIN_VALUE;它代表int所能表示的最小值 0x80000000(1000 0000 0000 0000 0000 0000 0000 0000)
在计算机的运算中,- 号运算表示各二制位取反再加1,也就是说 b =-a 在计算机内部是 b = ~a + 1 这样处理的,
则Integer.MIN_VALUE,1000 0000 0000 0000 0000 0000 0000 0000 
                                                  取反 0111 1111 1111 1111 1111 1111 1111 1111(取反之后变成了Integer.MAX_VALUE) 
                                                  加1 1000 0000 0000 0000 0000 0000 0000 0000 (-Integer.MIN_VALUE(与原来的结果一样))
Integer.MAX_VALUE+1=Integer.MIN_VALUE
*/	
		
//      '/'除以:即取商;'%'模以:即取余数	
		//计算最大数字是几位数
		int maxLength=(max+"").length();//数字加“”变成字符串 求字符串长度即可求位数
		//用于临时存储数据的数组
		int[][] temp=new int[10][a.length];//二维数组,解决了创建十个数组的问题,a.length位置必须填上,防止空指针异常
		//用于记录在temp中相应的数组中存放的数字的数量
		int[] counts=new int[10] ;
		
		//根据最大长度的数字决定比较次数
		for(int i=0,n=1;i<maxLength;i++,n*=10) {
			//把每一个数字分别计算余数,0次取个位数
			for(int j=0;j<a.length;j++) {
				int ys=a[j]/n%10;//取得余数
				temp[ys][counts[ys]]=a[j];
				//记录数量变化
				counts[ys]++;		
			}
			
			//记录取得的元素需要放的位置
			int index=0;
			//把数字取出来
			for(int k=0;k<counts.length;k++) {
				//记录数量的数组中,当前余数记录的数量不为0时,取出数字
				if(counts[k]!=0) {
					//循环取出数字
					for(int l=0;l<counts[k];l++) {
						a[index]=temp[k][l];
						//记录下一个位置
						index++;
					}
					//把数量置零
					counts[k]=0;
				}
			}	
		}	
	}
//基数排序的队列实现======================================================================
	public static void radixQueueSort(int[] a) {
		//找到最大的数字
		int max=Integer.MIN_VALUE;
		for(int i=0;i<a.length;i++) {
			if(a[i]>max) {
				max=a[i];
			}
		}
		//计算最大数字是几位数
		int maxLength=(max+"").length();//数字加“”变成字符串 求字符串长度即可求位数
		//用于临时存储数据的10个队列
		MyQueue[] temp=new MyQueue[10];
		//队列底层实现是数组
		//为队列数组赋值,否则队列对象是null
		for(int i=0;i<temp.length;i++) {
			temp[i]=new MyQueue();
		}
		//根据最大长度的数字决定比较趟数
		for(int i=0,n=1;i<maxLength;i++,n*=10) {
			//把每一个数字分别计算余数
			for(int j=0;j<a.length;j++) {
				int ys=a[j]/n%10;
				//n=1取得个位数,n=10取得十位数,n=100取得百位数、、
				//将当前遍历的数据放入指定的队列中
				temp[ys].add(a[j]);		
			}
			
			//记录取得的元素需要放的位置
			int index=0;
			//把数字取出来
			for(int k=0;k<temp.length;k++) {
				//记录数量的数组中,当前余数记录的数量不为0时,取出数字
				while(!temp[k].isEmpty()) {
					a[index]=temp[k].poll();
					index++;				
				}
			}	
		}	
	}
}
版权声明:本文为qq_38654591原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38654591/article/details/90677207

智能推荐

使用欧几里得算法解决问题——求字符串的最大公因子(力扣第1071题)(JavaScript解法)

1、欧几里得算法的思想 基于辗转相除法的原理,具体做法:用较大数除以较小数,再用出现的余数(第一个余数)去除除数,,再用出现的余数(第二个余数)去除第一个余数,如此仿佛,直到最后一个余数为0 2、算法流程 3、JavaScript实现欧几里得算法 4、使用欧几里得算法解决问题 力扣1071字符串的最大公因子 题目描述: 对于字符串 S 和 T,只有在 S = T + … + T(T ...

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

猜你喜欢

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...