大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > java的排序算法

java的排序算法

关键词:Javajava的排序算法  阅读(580) 赞(16)

[摘要]本文主要是对java的排序算法的讲解,希望对大家学习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.}



相关评论