黑马程序员技术交流社区

标题: 多种java排序方法，好用就收了吧 [打印本页]

作者: 马年出黑马 时间: 2014-4-2 00:17
标题: 多种java排序方法，好用就收了吧
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

作者: 马年出黑马 时间: 2014-4-2 00:18
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 }

作者: ☆枫の云 时间: 2014-4-2 09:11
感谢分享

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2