JAVA高级

http://java.chinaitlab.com/advance/910025_2.html

Java代码

    1.插入排序:

    2.

    3.1.package org.rut.util.algorithm.support;

    4.2.import org.rut.util.algorithm.SortUtil;

    5.3.4.public class InsertSort implements SortUtil.Sort{

    6.5.    /* (non-Javadoc)

    7.6.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    8.7.     */

    9.8.    public void sort(int[] data) {

    10.9.        int temp;

    11.10.        for(int i=1;i<data.length;i++){

    12.11.            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){

    13.12.                SortUtil.swap(data,j,j-1);

    14.13.            }

    15.14.        }

    16.15.    }

    17.16.}

    18.17.冒泡排序:

    19.

    20.1.package org.rut.util.algorithm.support;

    21.2.import org.rut.util.algorithm.SortUtil;

    22.3.4.public class BubbleSort implements SortUtil.Sort{

    23.5.    /* (non-Javadoc)

    24.6.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    25.7.     */

    26.8.    public void sort(int[] data) {

    27.9.        int temp;

    28.10.        for(int i=0;i<data.length;i++){

    29.11.            for(int j=data.length-1;j>i;j--){

    30.12.                if(data[j]<data[j-1]){

    31.13.                    SortUtil.swap(data,j,j-1);

    32.14.                }

    33.15.            }

    34.16.        }

    35.17.    }

    36.18.}

    37.19.选择排序:

    38.1.package org.rut.util.algorithm.support;

    39.2.import org.rut.util.algorithm.SortUtil;

    40.3.4.public class SelectionSort implements SortUtil.Sort {

    41.5.    /*

    42.6.     * (non-Javadoc)

    43.7.     *

    44.8.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    45.9.     */

    46.10.    public void sort(int[] data) {

    47.11.        int temp;

    48.12.        for (int i = 0; i < data.length; i++) {

    49.13.            int lowIndex = i;

    50.14.            for (int j = data.length - 1; j > i; j--) {

    51.15.                if (data[j] < data[lowIndex]) {

    52.16.                    lowIndex = j;

    53.17.                }

    54.18.            }

    55.19.            SortUtil.swap(data,i,lowIndex);

    56.20.        }

    57.21.    }

    58.22.}

    59.23.Shell排序:

    60.1.package org.rut.util.algorithm.support;

    61.2.import org.rut.util.algorithm.SortUtil;

    62.3.4.public class ShellSort implements SortUtil.Sort{

    63.5.    /* (non-Javadoc)

    64.6.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    65.7.     */

    66.8.    public void sort(int[] data) {

    67.9.        for(int i=data.length/2;i>2;i/=2){

    68.10.            for(int j=0;j<i;j++){

    69.11.                insertSort(data,j,i);

    70.12.            }

    71.13.        }

    72.14.        insertSort(data,0,1);

    73.15.    }

    74.16.    /**

    75.17.     * @param data

    76.18.     * @param j

    77.19.     * @param i

    78.20.     */

    79.21.    private void insertSort(int[] data, int start, int inc) {

    80.22.        int temp;

    81.23.        for(int i=start+inc;i<data.length;i+=inc){

    82.24.            for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){

    83.25.                SortUtil.swap(data,j,j-inc);

    84.26.            }

    85.27.        }

    86.28.    }

    87.29.}

    88.30.快速排序:

    89.1.package org.rut.util.algorithm.support;

    90.2.import org.rut.util.algorithm.SortUtil;

    91.3.4.public class QuickSort implements SortUtil.Sort{

    92.5.    /* (non-Javadoc)

    93.6.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    94.7.     */

    95.8.    public void sort(int[] data) {

    96.9.        quickSort(data,0,data.length-1);

    97.10.    }

    98.11.    private void quickSort(int[] data,int i,int j){

    99.12.        int pivotIndex=(i+j)/2;

    100.13.        //swap 14.        SortUtil.swap(data,pivotIndex,j);

    101.15.

    102.16.        int k=partition(data,i-1,j,data[j]);

    103.17.        SortUtil.swap(data,k,j);

    104.18.        if((k-i)>1) quickSort(data,i,k-1);

    105.19.        if((j-k)>1) quickSort(data,k+1,j);

    106.20.

    107.21.    }

    108.22.    /**

    109.23.     * @param data

    110.24.     * @param i

    111.25.     * @param j

    112.26.     * @return

    113.27.     */

    114.28.    private int partition(int[] data, int l, int r,int pivot) {

    115.29.        do{

    116.30.           while(data[++l]<pivot);

    117.31.           while((r!=0)&&data[--r]>pivot);

    118.32.           SortUtil.swap(data,l,r);

    119.33.        }

    120.34.        while(l<r);

    121.35.        SortUtil.swap(data,l,r);

    122.36.        return l;

    123.37.    }

    124.38.}

    125.39.改进后的快速排序:

    126.1.package org.rut.util.algorithm.support;

    127.2.import org.rut.util.algorithm.SortUtil;

    128.3.4.public class ImprovedQuickSort implements SortUtil.Sort {

    129.5.    private static int MAX_STACK_SIZE=4096;

    130.6.    private static int THRESHOLD=10;

    131.7.    /* (non-Javadoc)

    132.8.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    133.9.     */

    134.10.    public void sort(int[] data) {

    135.11.        int[] stack=new int[MAX_STACK_SIZE];

    136.12.

    137.13.        int top=-1;

    138.14.        int pivot;

    139.15.        int pivotIndex,l,r;

    140.16.

    141.17.        stack[++top]=0;

    142.18.        stack[++top]=data.length-1;

    143.19.

    144.20.        while(top>0){

    145.21.            int j=stack[top--];

    146.22.            int i=stack[top--];

    147.23.

    148.24.            pivotIndex=(i+j)/2;

    149.25.            pivot=data[pivotIndex];

    150.26.

    151.27.            SortUtil.swap(data,pivotIndex,j);

    152.28.

    153.29.            //partition 30.            l=i-1;

    154.31.            r=j;

    155.32.            do{

    156.33.                while(data[++l]<pivot);

    157.34.                while((r!=0)&&(data[--r]>pivot));

    158.35.                SortUtil.swap(data,l,r);

    159.36.            }

    160.37.            while(l<r);

    161.38.            SortUtil.swap(data,l,r);

    162.39.            SortUtil.swap(data,l,j);

    163.40.

    164.41.            if((l-i)>THRESHOLD){

    165.42.                stack[++top]=i;

    166.43.                stack[++top]=l-1;

    167.44.            }

    168.45.            if((j-l)>THRESHOLD){

    169.46.                stack[++top]=l+1;

    170.47.                stack[++top]=j;

    171.48.            }

    172.49.

    173.50.        }

    174.51.        //new InsertSort().sort(data); 52.        insertSort(data);

    175.53.    }

    176.54.    /**

    177.55.     * @param data

    178.56.     */

    179.57.    private void insertSort(int[] data) {

180.58.        int temp;

    181.59.        for(int i=1;i<data.length;i++){

    182.60.            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){

    183.61.                SortUtil.swap(data,j,j-1);

    184.62.            }

    185.63.        }

    186.64.    }

    187.65.}

    188.66.归并排序:

    189.1.package org.rut.util.algorithm.support;

    190.2.import org.rut.util.algorithm.SortUtil;

    191.3.4.public class MergeSort implements SortUtil.Sort{

    192.5.    /* (non-Javadoc)

    193.6.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    194.7.     */

    195.8.    public void sort(int[] data) {

    196.9.        int[] temp=new int[data.length];

    197.10.        mergeSort(data,temp,0,data.length-1);

    198.11.    }

    199.12.

    200.13.    private void mergeSort(int[] data,int[] temp,int l,int r){

    201.14.        int mid=(l+r)/2;

    202.15.        if(l==r) return ;

    203.16.        mergeSort(data,temp,l,mid);

    204.17.        mergeSort(data,temp,mid+1,r);

    205.18.        for(int i=l;i<=r;i++){

    206.19.            temp[i]=data[i];

    207.20.        }

    208.21.        int i1=l;

    209.22.        int i2=mid+1;

    210.23.        for(int cur=l;cur<=r;cur++){

    211.24.            if(i1==mid+1)

    212.25.                data[cur]=temp[i2++];

    213.26.            else if(i2>r)

    214.27.                data[cur]=temp[i1++];

    215.28.            else if(temp[i1]<temp[i2])

    216.29.                data[cur]=temp[i1++];

    217.30.            else

    218.31.                data[cur]=temp[i2++];

    219.32.        }

    220.33.    }

    221.34.}

    222.35.改进后的归并排序:

    223.

    224.1.package org.rut.util.algorithm.support;

    225.2.import org.rut.util.algorithm.SortUtil;

    226.3.4.public class ImprovedMergeSort implements SortUtil.Sort {

    227.5.    private static final int THRESHOLD = 10;

    228.6.    /*

    229.7.     * (non-Javadoc)

    230.8.     *

    231.9.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    232.10.     */

    233.11.    public void sort(int[] data) {

    234.12.        int[] temp=new int[data.length];

    235.13.        mergeSort(data,temp,0,data.length-1);

    236.14.    }

    237.15.    private void mergeSort(int[] data, int[] temp, int l, int r) {

    238.16.        int i, j, k;

    239.17.        int mid = (l + r) / 2;

    240.18.        if (l == r)

    241.19.            return;

    242.20.        if ((mid - l) >= THRESHOLD)

    243.21.            mergeSort(data, temp, l, mid);

    244.22.        else

    245.23.            insertSort(data, l, mid - l + 1);

    246.24.        if ((r - mid) > THRESHOLD)

    247.25.            mergeSort(data, temp, mid + 1, r);

    248.26.        else

    249.27.            insertSort(data, mid + 1, r - mid);

    250.28.        for (i = l; i <= mid; i++) {

    251.29.            temp[i] = data[i];

    252.30.        }

    253.31.        for (j = 1; j <= r - mid; j++) {

    254.32.            temp[r - j + 1] = data[j + mid];

    255.33.        }

    256.34.        int a = temp[l];

    257.35.        int b = temp[r];

    258.36.        for (i = l, j = r, k = l; k <= r; k++) {

    259.37.            if (a < b) {

    260.38.                data[k] = temp[i++];

    261.39.                a = temp[i];

    262.40.            } else {

    263.41.                data[k] = temp[j--];

    264.42.                b = temp[j];

    265.43.            }

    266.44.        }

    267.45.    }

    268.46.    /**

    269.47.     * @param data

    270.48.     * @param l

    271.49.     * @param i

    272.50.     */

    273.51.    private void insertSort(int[] data, int start, int len) {

    274.52.        for(int i=start+1;i<start+len;i++){

    275.53.            for(int j=i;(j>start) && data[j]<data[j-1];j--){

    276.54.                SortUtil.swap(data,j,j-1);

    277.55.            }

    278.56.        }

    279.57.    }

    280.58.}

    281.59.堆排序:

    282.1.package org.rut.util.algorithm.support;

    283.2.import org.rut.util.algorithm.SortUtil;

    284.3.4.public class HeapSort implements SortUtil.Sort{

    285.5.    /* (non-Javadoc)

    286.6.     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

    287.7.     */

    288.8.    public void sort(int[] data) {

    289.9.        MaxHeap h=new MaxHeap();

    290.10.        h.init(data);

    291.11.        for(int i=0;i<data.length;i++)

    292.12.            h.remove();

    293.13.        System.arraycopy(h.queue,1,data,0,data.length);

    294.14.    }

    295.15.16.     private static class MaxHeap{

    296.17.

    297.18.

    298.19.        void init(int[] data){

    299.20.            this.queue=new int[data.length+1];

    300.21.            for(int i=0;i<data.length;i++){

    301.22.                queue[++size]=data[i];

    302.23.                fixUp(size);

    303.24.            }

    304.25.        }

    305.26.

    306.27.        private int size=0;

    307.28.        private int[] queue;

    308.29.

    309.30.        public int get() {

    310.31.            return queue[1];

    311.32.        }

    312.33.        public void remove() {

    313.34.            SortUtil.swap(queue,1,size--);

    314.35.            fixDown(1);

    315.36.        }

    316.37.        //fixdown 38.        private void fixDown(int k) {

    317.39.            int j;

    318.40.            while ((j = k << 1) <= size) {

    319.41.                if (j < size && queue[j]<queue[j+1])

    320.42.                    j++;

    321.43.                if (queue[k]>queue[j]) //不用交换 44.                    break;

    322.45.                SortUtil.swap(queue,j,k);

    323.46.                k = j;

    324.47.            }

    325.48.        }

    326.49.        private void fixUp(int k) {

    327.50.            while (k > 1) {

    328.51.                int j = k >> 1;

    329.52.                if (queue[j]>queue[k])

    330.53.                    break;

    331.54.                SortUtil.swap(queue,j,k);

    332.55.                k = j;

    333.56.            }

    334.57.        }

    335.58.    }

    336.59.}

    337.60.SortUtil:

    338.1.package org.rut.util.algorithm;

    339.2.import org.rut.util.algorithm.support.BubbleSort;

    340.3.import org.rut.util.algorithm.support.HeapSort;

    341.4.import org.rut.util.algorithm.support.ImprovedMergeSort;

    342.5.import org.rut.util.algorithm.support.ImprovedQuickSort;

    343.6.import org.rut.util.algorithm.support.InsertSort;

    344.7.import org.rut.util.algorithm.support.MergeSort;

    345.8.import org.rut.util.algorithm.support.QuickSort;

    346.9.import org.rut.util.algorithm.support.SelectionSort;

    347.10.import org.rut.util.algorithm.support.ShellSort;

    348.11.12.public class SortUtil {

    349.13.    public final static int INSERT = 1;

    350.14.    public final static int BUBBLE = 2;

    351.15.    public final static int SELECTION = 3;

    352.16.    public final static int SHELL = 4;

    353.17.    public final static int QUICK = 5;

    354.18.    public final static int IMPROVED_QUICK = 6;

    355.19.    public final static int MERGE = 7;

    356.20.    public final static int IMPROVED_MERGE = 8;

    357.21.    public final static int HEAP = 9;

    358.22.    public static void sort(int[] data) {

    359.23.        sort(data, IMPROVED_QUICK);

    360.24.    }

    361.25.    private static String[] name={

    362.26.            “insert”,“bubble”,“selection”,“shell”,“quick”,“improved_quick”,“merge”,“improved_merge”,“heap”

    363.27.    };

    364.28.

    365.29.    private static Sort[] impl=new Sort[]{

    366.30.            new InsertSort(),

    367.31.            new BubbleSort(),

    368.32.            new SelectionSort(),

    369.33.            new ShellSort(),

    370.34.            new QuickSort(),

    371.35.            new ImprovedQuickSort(),

    372.36.            new MergeSort(),

    373.37.            new ImprovedMergeSort(),

    374.38.            new HeapSort()

    375.39.    };

    376.40.    public static String toString(int algorithm){

    377.41.        return name[algorithm-1];

    378.42.    }

    379.43.

    380.44.    public static void sort(int[] data, int algorithm) {

    381.45.        impl[algorithm-1].sort(data);

    382.46.    }

    383.47.    public static interface Sort {

    384.48.        public void sort(int[] data);

    385.49.    }

    386.50.    public static void swap(int[] data, int i, int j) {

    387.51.        int temp = data[i];

    388.52.        data[i] = data[j];

    389.53.        data[j] = temp;

    390.54.    }

    391.55.}