代码如下:
import java.util.BitSet;
import com.sun.java_cup.internal.internal_error;
public class Sort
{
private static boolean[] temp=new boolean[10000];
/**
* @notice 注意参数中的array数组中的每个元素大小不能超过9999,而且不能有重复元素。
* 同时也就意味着array数组大小不能超过10000,其中元素大小在0-9999的这样一个范围。
*/
public void sort(int[] array)
{
init();
for(int i=0;i<array.length;i++)
{
temp[array[i]]=true;
}
int loc=0;
for(int j=0;j<temp.length;j++)
{
if(temp[j])
array[loc++]=j;
}
}
private void init()//其实在此方法中通过传一个整数可以剪枝,而整数为array数组中元素的最大值
{
for(int i=0;i<temp.length;i++)
temp[i]=false;
}
public void print(int[] array)
{
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
}
public static void main(String[] args)
{
Sort sort=new Sort();
int array[]=new int[]{3,5,1,2,10,88,25,66};
sort.print(array);
sort.sort(array);
sort.print(array);
}
}
*****************运行结果*****************
3 5 1 2 10 88 25 66
1 2 3 5 10 25 66 88
今天在看《编程珠玑》开始的时候,作者提到了位示图的数据结构,受其启发想到了这样一种排序方法,不过这种排序算法对传入的数组有着严格要求,不能重复,而且数组中元素的数值范围受辅助数组的大小的制约,但是此排序算法相对来说还是很快的,时间复杂度为O(n)。感觉美中不足的是貌似主流编程语言中没有提供一种bit的数据类型,不然会大大减小前边提到的元素数值范围所受的限制。本人还是一位刚入职的菜鸟,鉴于所学有限,不足之处望大家能多多指正。
分享到:
相关推荐
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
一种O_n_nlog_2m_时间复杂度的排序算法.pdf
时间复杂度达到O(n)的不同于sort给予比较的O(nlogn)排序,是基于计数的一种线性排序方法,效率非常优秀。
算法设计与分析 一PRESETATION 仅做参考,请勿copy冲查重塔峰 排序算法性能分析 ...但注意理论上快速排序的空间复杂度较高为O(n),且最坏情况时时间复杂度也达到了O(n2)。所以快速算法也较为常用。
冒泡排序的时间复杂度为O(n^2),其中n是待排序数组的长度。 冒泡排序的基本思想是通过多次比较和交换,将最大的元素逐渐“冒泡”到数组的末尾。在每一轮的比较中,如果前一个元素大于后一个元素,则进行交换。通过...
归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列 归并排序时间复杂度 归并排序的时间复杂度是O...
冒泡排序,是指计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列...
快速排序在平均情况下的时间复杂度为O(nlogn),最坏情况下的时间复杂度为O(n^2),但通过随机选择基准元素可以将其最坏情况的发生概率降低。此外,快速排序是一种原地排序算法,不需要额外的存储空间。
冒泡排序,是指计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列...
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
算法时间复杂度O(n2)--[n的平方] 4、折半插入排序 折半插入排序是对插入排序的改进,主要通过二分查找,获得插入的位置 折半插入是一种稳定的排序 排序时间复杂度O(n^2)附加空间O(1) 5、快速排序 快速排序是不稳定的...
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
希尔排序是一种改进的插入排序算法,它的基本...希尔排序的时间复杂度为O(n^2),但实际上它的性能比插入排序要好得多,特别是在大型列表上。希尔排序的性能取决于间隔序列的选择,但是目前还没有一种最优的间隔序列。
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有 使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 ...
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
时间复杂度:冒泡排序的时间复杂度为O(n^2),其中n是待排序序列的长度。这是因为冒泡排序需要进行多轮遍历,并且每一轮遍历都需要比较和交换相邻元素。 稳定性:冒泡排序是一种稳定的排序算法,即相等元素的顺序在...
选择排序的时间复杂度为O(n^2),其中n表示待排序的元素个数。 虽然选择排序在效率上不如其他一些排序算法(如快速排序、归并排序等),但它的实现简单,且对于小规模的数据排序非常适用。在处理一些特定问题时,...