时间复杂度接近O(n)的三种排序算法

这篇具有很好参考价值的文章主要介绍了时间复杂度接近O(n)的三种排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.桶排序

桶排序,顾名思义,会用到“桶”,核心思想是将要排序的数据分到几个有
序的桶里,每个桶内的数据再单独进行排序。桶内排完序之后,再把每个桶内的数据按照顺序依次
取出,组成的序列就是有序的了。

桶排序对要排序数据的要求是非常苛刻的。
首先,要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。这样
每个桶内的数据都排序完之后,桶与桶之间的数据不需要再进行排序。

其次,数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后,有些桶内的数据非常
多,有些非常少,很不平均,那桶内数据排序的时间复杂度就不是常量级了。在极端情况下,如果
数据都被划分到一个桶内,那就退化为O(nlogn)的排序算法了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内
存有限,无法将数据全部加载到内存中。
时间复杂度接近O(n)的三种排序算法,数据结构与算法,排序算法,算法,java

/**
 * 桶排序
 * 原地排序:否
 * 稳定排序:是
 * 空间复杂度:
 * 时间复杂度:O(n)
 */
public class BucketSort {
	public static void main(String[] args) {
		int[] arr = { 1, 45, 32, 23, 22, 31, 47, 24, 4, 15 };
		bucketSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
	//存数区间0-9,10-19,20-29,30-39,40-49
	public static void bucketSort(int[] arr) {
		ArrayList bucket[] = new ArrayList[5];
		
		//初始化桶
		for(int i=0;i<bucket.length;i++) {
			bucket[i] = new ArrayList<Integer>();
		}
		
		//像桶内放入数据
		for(int i=0;i<arr.length;i++) {
			int index = arr[i]/10;
			bucket[index].add(arr[i]);
		}
		
		int index = 0;
		for(int i=0;i<bucket.length;i++) {
			bucket[i].sort(null);//对每个桶进行排序
			for(int j=0;j<bucket[i].size();j++) {
				arr[index++] = (int) bucket[i].get(j);
			}
		}
	}
}

2.计数排序

计数排序可以理解为是桶排序的一种特殊情况。当要排序的n个数据,所处的范围并不大的
时候,比如最大值是k,我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的,省掉了桶
内排序的时间。

计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,
就不适合用计数排序了。而且,计数排序只能给非负整数排序,如果要排序的数据是其他类型的,
要将其在不改变相对大小的情况下,转化为非负整数。
假定有原始数组A[8],它们分别是:2,5,3,0,2,3,0,3。数据范围从0-5

先用一个数组大小为6的数组C来存储在k值上数据有几个。
时间复杂度接近O(n)的三种排序算法,数据结构与算法,排序算法,算法,java

接着对数组顺序求和,C数组存储的数据就变成了,C[k]里存储小于等于分数k的的数据。
时间复杂度接近O(n)的三种排序算法,数据结构与算法,排序算法,算法,java

定义临时数组R,依次扫描数组原始数组A,将数据A入到R[C[k]]位置上,同时C[k]位置上的数据要减掉1,最后将R数组复制到原始数组A中。
时间复杂度接近O(n)的三种排序算法,数据结构与算法,排序算法,算法,java

/**
 * 计数排序
 * 原地排序:否
 * 稳定排序:是
 * 空间复杂度:O(k+n) k为数据范围大小
 * 时间复杂度:O(n+k)
 */
public class CountSort {
	public static void main(String[] args) {
		int[] arr = new int[]{5,3,1,3,2,8,6,9,10,4,6,4,8,10,7,4,2,1,6,7};
		CountingSort(arr,arr.length);
		System.out.println(Arrays.toString(arr));
	}
	
	public static void CountingSort(int[] a,int n) {
		if(n<=-1) return;
		
		//查找数组中最大值
		int max = a[0];
		for(int i=1;i<a.length;i++) {
			if(max<a[i]) {
				max = a[i];
			}
		}
		
		//申请一个计数数组C下标为0到max
		int[] c = new int[max+1];
		for(int i=0;i<c.length;i++) {
			c[i] = 0;
		}
		
		//计算每个元素的个数,放入数组C中
		for(int i=0;i<a.length;i++) {
			c[a[i]]++;
		}
		
		//依次累加
		for(int i=0;i<max;i++) {
			c[i+1] = c[i]+c[i+1];
		}
		
		//临时数组R,存储排序之后的数组
		int[] r = new int[a.length];
		//计数排序的关键步骤
		for(int i=a.length-1;i>=0;i--) {
			int index = c[a[i]]-1;
			r[index] = a[i];
			c[a[i]]--;
		}
		
		//将结果拷贝给a数组
		for(int i=0;i<a.length;i++) {
			a[i] = r[i];
		}
	}
}

3.基数排序

先按照数据最后以位来排序,然后,再按照倒数第二位重新排序,以此类推,最后按照第一位重新排序。经过多次排序之后,数据就都有序了。如果数据长度不一致,需要补齐数据到相同长短。

基数排序对要排序的数据是有要求的,需要可以分割出独立的“位”来比较,而且位之间有递进的关系,如果a数据的高位比b数据大,那剩下的低位就不需要较了。除此之外,每一位的数据范围不能太大,才可以用线性排序算法来排序,否则,基数排序的时间复杂度就无法做到O(n)了。
时间复杂度接近O(n)的三种排序算法,数据结构与算法,排序算法,算法,java文章来源地址https://www.toymoban.com/news/detail-624073.html

/**
 * 基数排序
 * 原地排序:否
 * 稳定排序:是
 * 空间复杂度:O(d+n) k为数据范围大小
 * 时间复杂度:O(dn) d是维数
 */
public class RadixSort {
	public static void main(String[] args) {
		int[] arrs = new int[] {153,26,78,342,123,241,96};
		
		int max = getMaxData(arrs);
		
		for(int exp=1;max/exp>0;exp=exp*10) {
			CountingSort(arrs,arrs.length,exp);
			System.out.println(Arrays.toString(arrs));
		}
	}
	
	public static int getMaxData(int[] a) {
		//查找数组中最大值
		int max = a[0];
		for(int i=1;i<a.length;i++) {
			if(max<a[i]) {
				max = a[i];
			}
		}
		return max;
	}
	
	public static void CountingSort(int[] a,int n,int exp) {
		if(n<=-1) return;
		
		//查找数组中最大值
		int max = (a[0]/exp)%10;
		for(int i=1;i<a.length;i++) {
			if(max<(a[i]/exp)%10) {
				max = (a[i]/exp)%10;
			}
		}
		
		//申请一个计数数组C下标为0到max
		int[] c = new int[max+1];
		for(int i=0;i<c.length;i++) {
			c[i] = 0;
		}
		
		//计算每个元素的个数,放入数组C中
		for(int i=0;i<a.length;i++) {
			c[(a[i]/exp)%10]++;
		}
		
		//依次累加
		for(int i=0;i<max;i++) {
			c[i+1] = c[i]+c[i+1];
		}
		
		//临时数组R,存储排序之后的数组
		int[] r = new int[a.length];
		//计数排序的关键步骤
		for(int i=a.length-1;i>=0;i--) {
			int index = c[(a[i]/exp)%10]-1;
			r[index] = a[i];
			c[(a[i]/exp)%10]--;
		}
		
		//将结果拷贝给a数组
		for(int i=0;i<a.length;i++) {
			a[i] = r[i];
		}
	}

}

到了这里,关于时间复杂度接近O(n)的三种排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包