java快速排序1000万无序数组256M JVM 耗时2s

自己动手写排序算法,快速排序是比较不好写的了~

 

[java][/java] view plaincopy

  1. import java.util.*;
  2. class Test{
  3.     public void quickSort(int[] arr,int low,int high){
  4.         if(low<high){
  5.             int i=low;
  6.             int j=high;
  7.             int x=arr[low];
  8.             while(i<j){
  9.                 while(i<j&&x<arr[j]){
  10.                     j–;
  11.                 }
  12.                 if(i<j)
  13.                     arr[i++]=arr[j];
  14.                 while(i<j&&x>arr[i]){
  15.                     i++;
  16.                 }
  17.                 if(i<j)
  18.                     arr[j–]=arr[i];
  19.             }
  20.             arr[i]=x;
  21.             quickSort(arr,low,i-1);
  22.             quickSort(arr,i+1,high);
  23.         }
  24.     }
  25.     public static void main(String[] args){
  26.         int[] arr=new int[10000000];
  27.         for(int i=0;i<arr.length;i++){
  28.             arr[i]=new Random().nextInt(100000000)+1;
  29.         }
  30.         long a=System.currentTimeMillis();
  31.         new Test().quickSort(arr, 0, arr.length-1);
  32.         long b=System.currentTimeMillis();
  33.         System.out.println(b-a);
  34.     }
  35. }

思路很简单

 

1.i =low; j = high; 将基准数x挖出形成第一个坑a[i]。

2.j–由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

5.   根据第四步得到的i值,执行递归直到low不再小于high,也就是递归到两个数字了,而且顺序是对的。

JVM 最大内存是256M。

标签