JAVA算法之求数组中第N小的数据

xiaoxiao2021-02-28  5

这个算法就是利用快速排序,每个分界点的位置就是它最终的位置,以每一次排序的分界点作为锚点,快排一次递归后,锚点前的都是小于锚点的数据,后面都是大于锚点的数据,假如要找第1000小的数据,第一层我们找到了分界点在500处,这时候只需要对500之后的数据再进行递归,就可以了。

实现代码及测试如下:

public static void getNumTest(int a[],int n){ quickSort(a,0,a.length-1,n-1); } private static void quickSort(int a[],int l,int r,int n){ if(r<=l){ if(r==n) System.out.println("第"+(n+1)+"小的数是:"+a[r]); return; } int p=a[l]; int i=l+1; int j=r; int m; while(true){ while(i<=r&&a[i]<p){ i++; } while(j>=l+1&&a[j]>p){ j--; } if(i> j) break; m=a[i]; a[i]=a[j]; a[j]=m; i++; j--; } a[l]=a[j]; a[j]=p; if(j<n){ quickSort(a,j+1,r,n); }else if(j>n){ quickSort(a,l,j-1,n); }else if(j==n) System.out.println("第"+(n+1)+"小的数是:"+a[j]); } public static void main(String args[]) { int a[]; // int n = (int) (Math.random() * 10 + 1); a = new int[100000]; for (int i = 0; i < 100000; i++) { a[i] = (int) (Math.random() * 1000000+1); } //System.out.println(Arrays.toString(a)); long t = System.currentTimeMillis(); //DecTest(a); getNumTest(a,100000); System.out.print("耗时:"); System.out.println(System.currentTimeMillis() - t); //System.out.println(Arrays.toString(a)); }
转载请注明原文地址: https://www.6miu.com/read-1750325.html

最新回复(0)