摘要：因?yàn)樗强焖倥判?，所以我想小?shù)據(jù)量并不能體現(xiàn)它的快速。正當(dāng)我要運(yùn)行程序并且統(tǒng)計(jì)其運(yùn)行時(shí)間時(shí)，悲劇發(fā)生了這是一個(gè)堆內(nèi)存溢出錯(cuò)誤。

閑來無事，順便寫一個(gè)快排的代碼。結(jié)果卻引發(fā)了java.OutOfMemoryError:Java heap space。
首先談?wù)効焖倥判?，這是一種在統(tǒng)計(jì)上很快的排序，他的核心思想是，在一個(gè)數(shù)組中隨便取一個(gè)數(shù)作為基準(zhǔn)(通常取最后一個(gè))，然后把整個(gè)數(shù)組劃分，把比基準(zhǔn)小或等于的數(shù)放在基準(zhǔn)之前，把大于基準(zhǔn)的數(shù)放在基準(zhǔn)之后。然后再分別對(duì)基準(zhǔn)之前的數(shù)組和基準(zhǔn)之后的數(shù)組進(jìn)行快速排序。
java 代碼：

void quicksort(int[] nums,int begin,int end)
    {
        if(end <= begin)return;
        int p = begin-1;
        for(int i = begin;i <= end;i++)
            if(nums[i] <= nums[end])
            {
                p++;
                int temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
            }
        quicksort(nums,begin,p-1);
        quicksort(nums,p+1,end);
    }

這里唯一難理解的就是這個(gè)p，這里的思想是，p及其左側(cè)都是小于等于基準(zhǔn)的數(shù)，而p的右側(cè)都是大于基準(zhǔn)的數(shù)。因此，遍歷這個(gè)數(shù)組的時(shí)候，若數(shù)大于基準(zhǔn)，則訪問下一個(gè)，否則把p+1，然后交換p和這個(gè)位置上的數(shù)，這樣就能成功劃分。

因?yàn)樗强焖倥判?，所以我想小?shù)據(jù)量并不能體現(xiàn)它的快速。因此，我使用了一個(gè)很大的數(shù)組，并且使用隨機(jī)數(shù)填充它。

Random random = new Random();
int[] nums = new int[ (1024*1024*1024) ];
for(int i = 0;i < nums.length;i++)
    nums[i] = random.nextInt(500000);

這個(gè)數(shù)組的大小是4個(gè)GB，因?yàn)橐粋€(gè)int是4B，而1024*1024是1M，而1024M是1G。
正當(dāng)我要運(yùn)行程序并且統(tǒng)計(jì)其運(yùn)行時(shí)間時(shí)，悲劇發(fā)生了！?。?br>Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
這是一個(gè)堆內(nèi)存溢出錯(cuò)誤。
于是我立馬想到一個(gè)解決方法，那就是擴(kuò)大堆內(nèi)存！
數(shù)組大小只有4GB，我現(xiàn)在給JVM進(jìn)程5000MB大小的堆內(nèi)存，也就是大約4.8GB的內(nèi)存，程序一定是沒問題的了。于是我添加了參數(shù)-Xms5000m。這個(gè)參數(shù)的意義是，最小堆內(nèi)存為5000MB。
然鵝，結(jié)果是
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
why???
要說明這個(gè)必須先知道java內(nèi)存結(jié)構(gòu)。
理解了java內(nèi)存結(jié)構(gòu)之后，才能明白。堆內(nèi)存又分為，新生代(Young)和老年代(Old)，而數(shù)組這種大對(duì)象一般是直接分配在老年代中。雖然我設(shè)置了5000MB的堆內(nèi)存，但是這5000MB的內(nèi)存并不都是給老年代的，老年代和新生代內(nèi)存的默認(rèn)比例是2，也就是說5000MB里只有2/3是老年代的，也就是3333MB≈3.25GB，這個(gè)大小仍然小于數(shù)組的4GB，因此現(xiàn)在我設(shè)置老-新比例為9，也就是老年代擁有5000MB*0.9=4500MB≈4.39GB，此時(shí)已經(jīng)大于數(shù)組所需要的內(nèi)存大?。?br>添加完參數(shù)-Xms5000m -XX:NewRatio=9后，我再次運(yùn)行程序，運(yùn)行成功?。?！經(jīng)過漫長的等待，輸出了排序的時(shí)間為1443.11s，也就是大約24分鐘?。?！

最后，java 核心代碼:

public static void main(String[] args) {
        Random random = new Random();

        int[] nums = new int[ (1024*1024*1024) ];
        for(int i = 0;i < nums.length;i++)
            nums[i] = random.nextInt(500000);
        long being = System.currentTimeMillis();
        quicksort(nums,0,nums.length-1);

        long end = System.currentTimeMillis();
        System.out.println(((double) (end-being))/1000+"s");



    }


   static void quicksort(int[] nums,int begin,int end)
    {
        if(end <= begin)return;
        int p = begin-1;
        for(int i = begin;i <= end;i++)
            if(nums[i] <= nums[end])
            {
                p++;
                int temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
            }
        quicksort(nums,begin,p-1);
        quicksort(nums,p+1,end);
    }