# Java 算法排序

victorzcs 贡献于2012-07-19

﻿插入排序: package org.rut.util.algorithm.support; import org.rut.util.algorithm.SortUtil; /**  * @author treeroot  * @since 2006-2-2  * @version 1.0  */ public class InsertSort implements SortUtil.Sort{     /* (non-Javadoc)      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])      */     public void sort(int[] data) {         int temp;         for(int i=1;i0)&&(data[j]i;j--){                 if(data[j] i; j--) {                 if (data[j] < data[lowIndex]) {                     lowIndex = j;                 }             }             SortUtil.swap(data,i,lowIndex);         }     } } Shell排序: package org.rut.util.algorithm.support; import org.rut.util.algorithm.SortUtil; /**  * @author treeroot  * @since 2006-2-2  * @version 1.0  */ public class ShellSort implements SortUtil.Sort{     /* (non-Javadoc)      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])      */     public void sort(int[] data) {         for(int i=data.length/2;i>2;i/=2){             for(int j=0;j=inc)&&(data[j]1) quickSort(data,i,k-1);         if((j-k)>1) quickSort(data,k+1,j);             }     /**      * @param data      * @param i      * @param j      * @return      */     private int partition(int[] data, int l, int r,int pivot) {         do{            while(data[++l]pivot);            SortUtil.swap(data,l,r);         }         while(l0){             int j=stack[top--];             int i=stack[top--];                         pivotIndex=(i+j)/2;             pivot=data[pivotIndex];                         SortUtil.swap(data,pivotIndex,j);                         //partition             l=i-1;             r=j;             do{                 while(data[++l]pivot));                 SortUtil.swap(data,l,r);             }             while(lTHRESHOLD){                 stack[++top]=i;                 stack[++top]=l-1;             }             if((j-l)>THRESHOLD){                 stack[++top]=l+1;                 stack[++top]=j;             }                     }         //new InsertSort().sort(data);         insertSort(data);     }     /**      * @param data      */     private void insertSort(int[] data) {         int temp;         for(int i=1;i0)&&(data[j]r)                 data[cur]=temp[i1++];             else if(temp[i1]= THRESHOLD)             mergeSort(data, temp, l, mid);         else             insertSort(data, l, mid - l + 1);         if ((r - mid) > THRESHOLD)             mergeSort(data, temp, mid + 1, r);         else             insertSort(data, mid + 1, r - mid);         for (i = l; i <= mid; i++) {             temp[i] = data[i];         }         for (j = 1; j <= r - mid; j++) {             temp[r - j + 1] = data[j + mid];         }         int a = temp[l];         int b = temp[r];         for (i = l, j = r, k = l; k <= r; k++) {             if (a < b) {                 data[k] = temp[i++];                 a = temp[i];             } else {                 data[k] = temp[j--];                 b = temp[j];             }         }     }     /**      * @param data      * @param l      * @param i      */     private void insertSort(int[] data, int start, int len) {         for(int i=start+1;istart) && data[j]queue[j]) //不用交换                     break;                 SortUtil.swap(queue,j,k);                 k = j;             }         }         private void fixUp(int k) {             while (k > 1) {                 int j = k >> 1;                 if (queue[j]>queue[k])                     break;                 SortUtil.swap(queue,j,k);                 k = j;             }         }     } }   SortUtil: package org.rut.util.algorithm; import org.rut.util.algorithm.support.BubbleSort; import org.rut.util.algorithm.support.HeapSort; import org.rut.util.algorithm.support.ImprovedMergeSort; import org.rut.util.algorithm.support.ImprovedQuickSort; import org.rut.util.algorithm.support.InsertSort; import org.rut.util.algorithm.support.MergeSort; import org.rut.util.algorithm.support.QuickSort; import org.rut.util.algorithm.support.SelectionSort; import org.rut.util.algorithm.support.ShellSort; /**  * @author treeroot  * @since 2006-2-2  * @version 1.0  */ public class SortUtil {     public final static int INSERT = 1;     public final static int BUBBLE = 2;     public final static int SELECTION = 3;     public final static int SHELL = 4;     public final static int QUICK = 5;     public final static int IMPROVED_QUICK = 6;     public final static int MERGE = 7;     public final static int IMPROVED_MERGE = 8;     public final static int HEAP = 9;     public static void sort(int[] data) {         sort(data, IMPROVED_QUICK);     }     private static String[] name={             "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"     };         private static Sort[] impl=new Sort[]{             new InsertSort(),             new BubbleSort(),             new SelectionSort(),             new ShellSort(),             new QuickSort(),             new ImprovedQuickSort(),             new MergeSort(),             new ImprovedMergeSort(),             new HeapSort()     };     public static String toString(int algorithm){         return name[algorithm-1];     }         public static void sort(int[] data, int algorithm) {         impl[algorithm-1].sort(data);     }     public static interface Sort {         public void sort(int[] data);     }     public static void swap(int[] data, int i, int j) {         int temp = data[i];         data[i] = data[j];         data[j] = temp;     } }