java算法题

发布网友发布时间：2022-04-21 17:58

共5个回答

热心网友时间：2023-10-02 00:23

快速排序一般来说比较适用于数据量大的情况
public class QuickSoft {

private void swap(int a[],int i,int j)
{
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}

private int partition(int a[],int p,int r)
{
int point = a[r];
//将小于等于point的元素移到左边区域
//将大于point的元素移到右边区域
int index=p;
for (int i = index; i < r; ++ i) {
if (a[i]-point <= 0) {
swap(a, index++, i);
}
}
swap(a,index,r);
return index;
}

public void qsort(int a[],int p,int r)
{
if(p< r)
{
//确定拆分点，并对数组元素进行移动
//这是快速排序算法的关键步骤
int q=partition(a,p,r);
//对左半段排序
qsort(a,p,q-1);
//对右半段排序
qsort(a,q+1,r);
}
}

public static void main(String[] args) {
//声明一个类
QuickSoft ms=new QuickSoft();
int len=10;
int a[]=new int[len];
//初始化a数组

System.out.println("原始数组如下：");
for(int i=0;i< a.length;i++)
{
//产生a.length个随机数
a[i] = (int)(Math.random()*100000);
System.out.println(a[i]);
}
System.out.println("---------------------");
System.out.println("第一次分组后");
ms.partition(a,0,len-1);
for(int i=0;i< a.length;i++)
{
System.out.println(a[i]);
}
System.out.println("---------------------");
//快速排序
ms.qsort(a, 0, len-1);

System.out.println("排序后的数组如下：");
for(int i=0;i< a.length;i++)
{
System.out.println(a[i]);
}

}
}

热心网友时间：2023-10-02 00:23

如果是不重复的1---1亿个数字，那么你知道这个数字是多少的时候它的位置就已经确定了。使用下面的方法应该是最快的（可能申请不到那么大的内存，你可以分片读入文件）：
public class SortXX {
private static int [] nums = new int[10000];

private static int[] sortedArray = new int[10000];

public static void main(String[] args) {
for(int i=0; i<nums.length; i++) {

sortedArray[nums[i]] = nums[i];

}

}

}
这个好像叫做什么水桶排序法，忘了，看下是不是你需要的。这个复杂度是On的

热心网友时间：2023-10-02 00:24

jdk提供了一个算法，Arrays.sort();平均速度貌似要比插入、快速之类的快很多

热心网友时间：2023-10-02 00:24

各种排序算法都有复杂度的公式，比较一下就知道了，比如冒泡排序，快速排序等

热心网友时间：2023-10-02 00:25

直接塞进 HashSet 里就ok了........