001        //插入排序:
002         
003        package org.rut.util.algorithm.support;
004         
005        import org.rut.util.algorithm.SortUtil;
006        /**
007         * @author treeroot
008         * @since 2006-2-2
009         * @version 1.0
010         */
011        public class InsertSort implements SortUtil.Sort{
012         
013            /** (non-Javadoc)
014             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
015             */
016            public void sort(int[] data) {
017                int temp;
018                for(int i=1;i<data.length;i++){
019                    for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
020                        SortUtil.swap(data,j,j-1);
021                    }
022                }      
023            }
024         
025        }
026        //冒泡排序:
027         
028         
029        for(var i=0; i<arr.length; i++) {   
030            for(var j=i+1; j<=arr.length-1; j++) {
031                if(eval(arr[i]) < eval(arr[j])) {      
032                    temp = arr[i];                     
033                    arr[i] = arr[j];                       
034                    arr[j] = temp;                                             
035                }
036            }
037        }
038         
039         
040         
041        package org.rut.util.algorithm.support;
042         
043        import org.rut.util.algorithm.SortUtil;
044         
045        /**
046         * @author treeroot
047         * @since 2006-2-2
048         * @version 1.0
049         */
050        public class BubbleSort implements SortUtil.Sort{
051         
052            /** (non-Javadoc)
053             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
054             */
055            public void sort(int[] data) {
056                int temp;
057                for(int i=0;i<data.length;i++){
058                    for(int j=data.length-1;j>i;j--){
059                        if(data[j]<data[j-1]){
060                            SortUtil.swap(data,j,j-1);
061                        }
062                    }
063                }
064            }
065         
066        }
067         
068        //选择排序:
069         
070        package org.rut.util.algorithm.support;
071         
072        import org.rut.util.algorithm.SortUtil;
073         
074        /**
075         * @author treeroot
076         * @since 2006-2-2
077         * @version 1.0
078         */
079        public class SelectionSort implements SortUtil.Sort {
080         
081            /**
082             * (non-Javadoc)
083             *
084             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
085             */
086            public void sort(int[] data) {
087                int temp;
088                for (int i = 0; i < data.length; i++) {
089                    int lowIndex = i;
090                    for (int j = data.length - 1; j > i; j--) {
091                        if (data[j] < data[lowIndex]) {
092                            lowIndex = j;
093                        }
094                    }
095                    SortUtil.swap(data,i,lowIndex);
096                }
097            }
098         
099        }
100         
101        //Shell排序:
102         
103        package org.rut.util.algorithm.support;
104         
105        import org.rut.util.algorithm.SortUtil;
106         
107        /**
108         * @author treeroot
109         * @since 2006-2-2
110         * @version 1.0
111         */
112        public class ShellSort implements SortUtil.Sort{
113         
114            /** (non-Javadoc)
115             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
116             */
117            public void sort(int[] data) {
118                for(int i=data.length/2;i>2;i/=2){
119                    for(int j=0;j<i;j++){
120                        insertSort(data,j,i);
121                    }
122                }
123                insertSort(data,0,1);
124            }
125         
126            /**
127             * @param data
128             * @param j
129             * @param i
130             */
131            private void insertSort(int[] data, int start, int inc) {
132                int temp;
133                for(int i=start+inc;i<data.length;i+=inc){
134                    for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
135                        SortUtil.swap(data,j,j-inc);
136                    }
137                }
138            }
139         
140        }
141         
142        //快速排序:
143         
144        package org.rut.util.algorithm.support;
145         
146        import org.rut.util.algorithm.SortUtil;
147         
148        /**
149         * @author treeroot
150         * @since 2006-2-2
151         * @version 1.0
152         */
153        public class QuickSort implements SortUtil.Sort{
154         
155            /** (non-Javadoc)
156             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
157             */
158            public void sort(int[] data) {
159                quickSort(data,0,data.length-1);      
160            }
161            private void quickSort(int[] data,int i,int j){
162                int pivotIndex=(i+j)/2;
163                //swap
164                SortUtil.swap(data,pivotIndex,j);
165                
166                int k=partition(data,i-1,j,data[j]);
167                SortUtil.swap(data,k,j);
168                if((k-i)>1) quickSort(data,i,k-1);
169                if((j-k)>1) quickSort(data,k+1,j);
170                
171            }
172            /**
173             * @param data
174             * @param i
175             * @param j
176             * @return
177             */
178            private int partition(int[] data, int l, int r,int pivot) {
179                do{
180                   while(data[++l]<pivot);
181                   while((r!=0)&&data[--r]>pivot);
182                   SortUtil.swap(data,l,r);
183                }
184                while(l<r);
185                SortUtil.swap(data,l,r);      
186                return l;
187            }
188         
189        }
190        //改进后的快速排序:
191         
192        package org.rut.util.algorithm.support;
193         
194        import org.rut.util.algorithm.SortUtil;
195         
196        /**
197         * @author treeroot
198         * @since 2006-2-2
199         * @version 1.0
200         */
201        public class ImprovedQuickSort implements SortUtil.Sort {
202         
203            private static int MAX_STACK_SIZE=4096;
204            private static int THRESHOLD=10;
205            /** (non-Javadoc)
206             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
207             */
208            public void sort(int[] data) {
209                int[] stack=new int[MAX_STACK_SIZE];
210                
211                int top=-1;
212                int pivot;
213                int pivotIndex,l,r;
214                
215                stack[++top]=0;
216                stack[++top]=data.length-1;
217                
218                while(top>0){
219                    int j=stack[top--];
220                    int i=stack[top--];
221                     
222                    pivotIndex=(i+j)/2;
223                    pivot=data[pivotIndex];
224                     
225                    SortUtil.swap(data,pivotIndex,j);
226                     
227                    //partition
228                    l=i-1;
229                    r=j;
230                    do{
231                        while(data[++l]<pivot);
232                        while((r!=0)&&(data[--r]>pivot));
233                        SortUtil.swap(data,l,r);
234                    }
235                    while(l<r);
236                    SortUtil.swap(data,l,r);
237                    SortUtil.swap(data,l,j);
238                     
239                    if((l-i)>THRESHOLD){
240                        stack[++top]=i;
241                        stack[++top]=l-1;
242                    }
243                    if((j-l)>THRESHOLD){
244                        stack[++top]=l+1;
245                        stack[++top]=j;
246                    }
247                     
248                }
249                //new InsertSort().sort(data);
250                insertSort(data);
251            }
252            /**
253             * @param data
254             */
255            private void insertSort(int[] data) {
256                int temp;
257                for(int i=1;i<data.length;i++){
258                    for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
259                        SortUtil.swap(data,j,j-1);
260                    }
261                }      
262            }
263         
264        }
265         
266        //归并排序:
267         
268        package org.rut.util.algorithm.support;
269         
270        import org.rut.util.algorithm.SortUtil;
271         
272        /**
273         * @author treeroot
274         * @since 2006-2-2
275         * @version 1.0
276         */
277        public class MergeSort implements SortUtil.Sort{
278         
279            /** (non-Javadoc)
280             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
281             */
282            public void sort(int[] data) {
283                int[] temp=new int[data.length];
284                mergeSort(data,temp,0,data.length-1);
285            }
286             
287            private void mergeSort(int[] data,int[] temp,int l,int r){
288                int mid=(l+r)/2;
289                if(l==r) return ;
290                mergeSort(data,temp,l,mid);
291                mergeSort(data,temp,mid+1,r);
292                for(int i=l;i<=r;i++){
293                    temp[i]=data[i];
294                }
295                int i1=l;
296                int i2=mid+1;
297                for(int cur=l;cur<=r;cur++){
298                    if(i1==mid+1)
299                        data[cur]=temp[i2++];
300                    else if(i2>r)
301                        data[cur]=temp[i1++];
302                    else if(temp[i1]<temp[i2])
303                        data[cur]=temp[i1++];
304                    else
305                        data[cur]=temp[i2++];           
306                }
307            }
308         
309        }
310         

311        //改进后的归并排序:
312         
313        package org.rut.util.algorithm.support;
314         
315        import org.rut.util.algorithm.SortUtil;
316         
317        /**
318         * @author treeroot
319         * @since 2006-2-2
320         * @version 1.0
321         */
322        public class ImprovedMergeSort implements SortUtil.Sort {
323         
324            private static final int THRESHOLD = 10;
325         
326            /**
327             * (non-Javadoc)
328             *
329             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
330             */
331            public void sort(int[] data) {
332                int[] temp=new int[data.length];
333                mergeSort(data,temp,0,data.length-1);
334            }
335         
336            private void mergeSort(int[] data, int[] temp, int l, int r) {
337                int i, j, k;
338                int mid = (l + r) / 2;
339                if (l == r)
340                    return;
341                if ((mid - l) >= THRESHOLD)
342                    mergeSort(data, temp, l, mid);
343                else
344                    insertSort(data, l, mid - l + 1);
345                if ((r - mid) > THRESHOLD)
346                    mergeSort(data, temp, mid + 1, r);
347                else
348                    insertSort(data, mid + 1, r - mid);
349         
350                for (i = l; i <= mid; i++) {
351                    temp[i] = data[i];
352                }
353                for (j = 1; j <= r - mid; j++) {
354                    temp[r - j + 1] = data[j + mid];
355                }
356                int a = temp[l];
357                int b = temp[r];
358                for (i = l, j = r, k = l; k <= r; k++) {
359                    if (a < b) {
360                        data[k] = temp[i++];
361                        a = temp[i];
362                    } else {
363                        data[k] = temp[j--];
364                        b = temp[j];
365                    }
366                }
367            }
368         
369            /**
370             * @param data
371             * @param l
372             * @param i
373             */
374            private void insertSort(int[] data, int start, int len) {
375                for(int i=start+1;i<start+len;i++){
376                    for(int j=i;(j>start) && data[j]<data[j-1];j--){
377                        SortUtil.swap(data,j,j-1);
378                    }
379                }
380            }
381         
382        }
383        //堆排序:
384         
385        package org.rut.util.algorithm.support;
386         
387        import org.rut.util.algorithm.SortUtil;
388         
389        /**
390         * @author treeroot
391         * @since 2006-2-2
392         * @version 1.0
393         */
394        public class HeapSort implements SortUtil.Sort{
395         
396            /** (non-Javadoc)
397             * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
398             */
399            public void sort(int[] data) {
400                MaxHeap h=new MaxHeap();
401                h.init(data);
402                for(int i=0;i<data.length;i++)
403                    h.remove();
404                System.arraycopy(h.queue,1,data,0,data.length);
405            }
406         
407         
408             private static class MaxHeap{
409                  
410                
411                void init(int[] data){
412                    this.queue=new int[data.length+1];
413                    for(int i=0;i<data.length;i++){
414                        queue[++size]=data[i];
415                        fixUp(size);
416                    }
417                }
418                  
419                private int size=0;
420         
421                private int[] queue;
422                         
423                public int get() {
424                    return queue[1];
425                }
426         
427                public void remove() {
428                    SortUtil.swap(queue,1,size--);
429                    fixDown(1);
430                }
431                //fixdown
432                private void fixDown(int k) {
433                    int j;
434                    while ((j = k << 1) <= size) {
435                        if (j < size && queue[j]<queue[j+1])
436                            j++;
437                        if (queue[k]>queue[j]) //不用交换
438                            break;
439                        SortUtil.swap(queue,j,k);
440                        k = j;
441                    }
442                }
443                private void fixUp(int k) {
444                    while (k > 1) {
445                        int j = k >> 1;
446                        if (queue[j]>queue[k])
447                            break;
448                        SortUtil.swap(queue,j,k);
449                        k = j;
450                    }
451                }
452         
453            }
454         
455        }
456         
457          
458         
459        //SortUtil:
460         
461        package org.rut.util.algorithm;
462         
463        import org.rut.util.algorithm.support.BubbleSort;
464        import org.rut.util.algorithm.support.HeapSort;
465        import org.rut.util.algorithm.support.ImprovedMergeSort;
466        import org.rut.util.algorithm.support.ImprovedQuickSort;
467        import org.rut.util.algorithm.support.InsertSort;
468        import org.rut.util.algorithm.support.MergeSort;
469        import org.rut.util.algorithm.support.QuickSort;
470        import org.rut.util.algorithm.support.SelectionSort;
471        import org.rut.util.algorithm.support.ShellSort;
472         
473        /**
474         * @author treeroot
475         * @since 2006-2-2
476         * @version 1.0
477         */
478        public class SortUtil {
479            public final static int INSERT = 1;
480         
481            public final static int BUBBLE = 2;
482         
483            public final static int SELECTION = 3;
484         
485            public final static int SHELL = 4;
486         
487            public final static int QUICK = 5;
488         
489            public final static int IMPROVED_QUICK = 6;
490         
491            public final static int MERGE = 7;
492         
493            public final static int IMPROVED_MERGE = 8;
494         
495            public final static int HEAP = 9;
496         
497            public static void sort(int[] data) {
498                sort(data, IMPROVED_QUICK);
499            }
500            private static String[] name={
501                    "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
502            };
503             
504            private static Sort[] impl=new Sort[]{
505                    new InsertSort(),
506                    new BubbleSort(),
507                    new SelectionSort(),
508                    new ShellSort(),
509                    new QuickSort(),
510                    new ImprovedQuickSort(),
511                    new MergeSort(),
512                    new ImprovedMergeSort(),
513                    new HeapSort()
514            };
515         
516            public static String toString(int algorithm){
517                return name[algorithm-1];
518            }
519             
520            public static void sort(int[] data, int algorithm) {
521                impl[algorithm-1].sort(data);
522            }
523         
524            public static interface Sort {
525                public void sort(int[] data);
526            }
527         
528            public static void swap(int[] data, int i, int j) {
529                int temp = data[i];
530                data[i] = data[j];
531                data[j] = temp;
532            }
533        }

感谢分享