1 package com.util;
  2 
  3 public class ArraysPrimitive {
  4     private ArraysPrimitive() {}
  5 
  6     /**
  7     * 對指(zhi)定的 int 型數(shu)組按數(shu)字(zi)升序(xu)(xu)進(jin)行排序(xu)(xu)。
  8      */
  9     public static void sort(int[] a) {
 10         sort1(a, 0, a.length);
 11    }
 12     
 13     /**
 14     * 對(dui)指定 int 型數組的指定范圍按數字升序(xu)進行排序(xu)。
 15      */
 16     public static void sort(int[] a, int fromIndex, int toIndex) {
 17        rangeCheck(a.length, fromIndex, toIndex);
 18         sort1(a, fromIndex, toIndex - fromIndex);
 19    }
 20 
 21     private static void sort1(int x[], int off, int len) {
 22         /*
 23         * 當待排(pai)序(xu)(xu)的數(shu)組中的元(yuan)素個數(shu)小(xiao)于 7 時，采用插(cha)入(ru)排(pai)序(xu)(xu) 。
 24         * 
 25         * 盡(jin)管插(cha)入(ru)排(pai)序(xu)(xu)的時間復(fu)雜(za)度為O(n^2),但是當數(shu)組元(yuan)素較(jiao)少時， 插(cha)入(ru)排(pai)序(xu)(xu)優(you)于快速(su)(su)排(pai)序(xu)(xu)，因為這時快速(su)(su)排(pai)序(xu)(xu)的遞歸操作影響性(xing)能。
 26          */
 27         if (len < 7) {
 28             for (int i = off; i < len + off; i++)
 29                 for (int j = i; j > off && x[j - 1] > x[j]; j--)
 30                     swap(x, j, j - 1);
 31             return;
 32        }
 33         /*
 34         * 當待排序(xu)的數(shu)組(zu)中的元(yuan)素(su)個(ge)數(shu)大(da)于(yu) 或等(deng)于(yu)7 時，采用快速排序(xu) 。
 35         * 
 36         * Choose a partition element, v
 37         * 選取一個(ge)劃分(fen)元(yuan)，V
 38         * 
 39         * 較好的選擇了劃分(fen)元(yuan)(基準元(yuan)素(su))。能夠(gou)將(jiang)數(shu)組(zu)分(fen)成大(da)致兩(liang)個(ge)相等(deng)的部分(fen)，避免出(chu)現(xian)最壞(huai)的情(qing)況。例如當數(shu)組(zu)有序(xu)的的情(qing)況下，
 40         * 選擇第一個(ge)元(yuan)素(su)作為(wei)劃分(fen)元(yuan)，將(jiang)使得算法的時間復雜度達到O(n^2).
 41          */
 42         // 當數組(zu)大小(xiao)為size=7時(shi) ，取數組(zu)中間元素作為劃(hua)分元。
 43         int m = off + (len >> 1);
 44         // 當數組(zu)大(da)小 7<size<=40時，取首、中、末 三個元(yuan)素中間(jian)大(da)小的元(yuan)素作為劃(hua)分元(yuan)。
 45         if (len > 7) {
 46             int l = off;
 47             int n = off + len - 1;
 48             /*
 49             * 當數(shu)組(zu)大小  size>40 時 ，從待排數(shu)組(zu)中(zhong)較均(jun)勻的選擇9個元(yuan)素，
 50             * 選出一(yi)個偽中(zhong)數(shu)做為劃(hua)分元(yuan)。
 51              */
 52             if (len > 40) {
 53                 int s = len / 8;
 54                 l = med3(x, l, l + s, l + 2 * s);
 55                 m = med3(x, m - s, m, m + s);
 56                 n = med3(x, n - 2 * s, n - s, n);
 57            }
 58             // 取出中(zhong)間(jian)大小的(de)元素(su)的(de)位(wei)置。
 59             m = med3(x, l, m, n); // Mid-size, med of 3
 60        }
 61         
 62         //得到(dao)劃分元V
 63         int v = x[m];
 64         
 65         // Establish Invariant: v* (<v)* (>v)* v*
 66         int a = off, b = a, c = off + len - 1, d = c;
 67         while (true) {
 68             while (b <= c && x[b] <= v) {
 69                 if (x[b] == v)
 70                     swap(x, a++, b);
 71                 b++;
 72            }
 73             while (c >= b && x[c] >= v) {
 74                 if (x[c] == v)
 75                     swap(x, c, d--);
 76                 c--;
 77            }
 78             if (b > c)
 79                 break;
 80             swap(x, b++, c--);
 81        }
 82         // Swap partition elements back to middle
 83         int s, n = off + len;
 84         s = Math.min(a - off, b - a);
 85         vecswap(x, off, b - s, s);
 86         s = Math.min(d - c, n - d - 1);
 87         vecswap(x, b, n - s, s);
 88         // Recursively sort non-partition-elements
 89         if ((s = b - a) > 1)
 90            sort1(x, off, s);
 91         if ((s = d - c) > 1)
 92             sort1(x, n - s, s);
 93    }
 94     
 95     /**
 96     * Swaps x[a] with x[b].
 97      */
 98     private static void swap(int x[], int a, int b) {
 99         int t = x[a];
100         x[a] = x[b];
101         x[b] = t;
102    }
103     
104     /**
105     * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
106      */
107     private static void vecswap(int x[], int a, int b, int n) {
108     for (int i=0; i<n; i++, a++, b++)
109        swap(x, a, b);
110    }
111     
112     /**
113     * Returns the index of the median of the three indexed integers.
114      */
115     private static int med3(int x[], int a, int b, int c) {
116         return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
117                 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
118    }
119 
120     /**
121     * Check that fromIndex and toIndex are in range, and throw an
122     * appropriate exception if they aren't.
123      */
124     private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
125         if (fromIndex > toIndex)
126             throw new IllegalArgumentException("fromIndex(" + fromIndex
127                     + ") > toIndex(" + toIndex + ")");
128         if (fromIndex < 0)
129             throw new ArrayIndexOutOfBoundsException(fromIndex);
130         if (toIndex > arrayLen)
131             throw new ArrayIndexOutOfBoundsException(toIndex);
132    }
133 }

1 package com.test;
 2 
 3 import com.util.ArraysPrimitive;
 4 
 5 public class ArraysTest {
 6     public static void main(String[] args) {
 7         int [] a={15,93,15,41,6,15,22,7,15,20};
 8        ArraysPrimitive.sort(a);
 9         for(int i=0;i<a.length;i++){
10             System.out.print(a[i]+",");
11        }
12         //結(jie)果：6,7,15,15,15,15,20,22,41,93,
13    }
14 }

1 package com.util;
  2 
  3 import java.lang.reflect.Array;
  4 
  5 public class ArraysObject {
  6     private static final int INSERTIONSORT_THRESHOLD = 7;
  7 
  8     private ArraysObject() {}
  9 
 10     public static void sort(Object[] a) {
 11         //java.lang.Object.clone()，理解(jie)深表復制和(he)淺(qian)表復制
 12         Object[] aux = (Object[]) a.clone();
 13         mergeSort(aux, a, 0, a.length, 0);
 14    }
 15 
 16     public static void sort(Object[] a, int fromIndex, int toIndex) {
 17        rangeCheck(a.length, fromIndex, toIndex);
 18         Object[] aux = copyOfRange(a, fromIndex, toIndex);
 19         mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
 20    }
 21 
 22     /**
 23     * Src is the source array that starts at index 0 
 24     * Dest is the (possibly larger) array destination with a possible offset 
 25     * low is the index in dest to start sorting 
 26     * high is the end index in dest to end sorting 
 27     * off is the offset to generate corresponding low, high in src
 28      */
 29     private static void mergeSort(Object[] src, Object[] dest, int low,
 30             int high, int off) {
 31         int length = high - low;
 32 
 33         // Insertion sort on smallest arrays
 34         if (length < INSERTIONSORT_THRESHOLD) {
 35             for (int i = low; i < high; i++)
 36                 for (int j = i; j > low && 
 37                         ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
 38                     swap(dest, j, j - 1);
 39             return;
 40        }
 41 
 42         // Recursively sort halves of dest into src
 43         int destLow = low;
 44         int destHigh = high;
 45         low += off;
 46         high += off;
 47         /*
 48         *  >>>：無符號右(you)移運算符
 49         *  expression1 &gt;>> expresion2：expression1的各個位向右(you)移expression2
 50         *  指(zhi)定的位數。右(you)移后左邊空出(chu)的位數用0來(lai)填充。移出(chu)右(you)邊的位被丟棄。
 51         *  例如：-14>>>2；  結果為(wei)：1073741820
 52          */
 53         int mid = (low + high) >>> 1;
 54         mergeSort(dest, src, low, mid, -off);
 55         mergeSort(dest, src, mid, high, -off);
 56 
 57         // If list is already sorted, just copy from src to dest. This is an
 58         // optimization that results in faster sorts for nearly ordered lists.
 59         if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
 60            System.arraycopy(src, low, dest, destLow, length);
 61             return;
 62        }
 63 
 64         // Merge sorted halves (now in src) into dest
 65         for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
 66             if (q >= high || p < mid
 67                     && ((Comparable) src[p]).compareTo(src[q]) <= 0)
 68                 dest[i] = src[p++];
 69             else
 70                 dest[i] = src[q++];
 71        }
 72    }
 73 
 74     /**
 75     * Check that fromIndex and toIndex are in range, and throw an appropriate
 76     * exception if they aren't.
 77      */
 78     private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
 79         if (fromIndex > toIndex)
 80             throw new IllegalArgumentException("fromIndex(" + fromIndex
 81                     + ") > toIndex(" + toIndex + ")");
 82         if (fromIndex < 0)
 83             throw new ArrayIndexOutOfBoundsException(fromIndex);
 84         if (toIndex > arrayLen)
 85             throw new ArrayIndexOutOfBoundsException(toIndex);
 86    }
 87 
 88     public static <T> T[] copyOfRange(T[] original, int from, int to) {
 89         return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
 90    }
 91 
 92     public static <T, U> T[] copyOfRange(U[] original, int from, int to,
 93             Class<? extends T[]> newType) {
 94         int newLength = to - from;
 95         if (newLength < 0)
 96             throw new IllegalArgumentException(from + " > " + to);
 97         T[] copy = ((Object) newType == (Object) Object[].class)
 98                 ? (T[]) new Object[newLength]
 99                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
100         System.arraycopy(original, from, copy, 0,
101                 Math.min(original.length - from, newLength));
102         return copy;
103    }
104 
105     /**
106     * Swaps x[a] with x[b].
107      */
108     private static void swap(Object[] x, int a, int b) {
109         Object t = x[a];
110         x[a] = x[b];
111         x[b] = t;
112    }
113 }

1 package com.test;
 2 
 3 import com.util.ArraysObject;
 4 
 5 public class ArraysObjectSortTest {
 6     public static void main(String[] args) {
 7         Student stu1=new Student(1001,100.0F);
 8         Student stu2=new Student(1002,90.0F);
 9         Student stu3=new Student(1003,90.0F);
10         Student stu4=new Student(1004,95.0F);
11         Student[] stus={stu1,stu2,stu3,stu4};
12         //Arrays.sort(stus);
13        ArraysObject.sort(stus);
14         for(int i=0;i<stus.length;i++){
15             System.out.println(stus[i].getId()+" : "+stus[i].getScore());
16        }
17         /* 1002 : 90.0
18         * 1003 : 90.0
19         * 1004 : 95.0
20         * 1001 : 100.0
21          */
22    }
23 }
24 class Student implements Comparable<Student>{
25     private int id;  //學號
26     private float score;  //成(cheng)績
27     public Student(){}
28     public Student(int id,float score){
29         this.id=id;
30         this.score=score;
31    }
32    @Override
33     public int compareTo(Student s) {
34         return (int)(this.score-s.getScore());
35    }
36     public int getId() {
37         return id;
38    }
39     public void setId(int id) {
40         this.id = id;
41    }
42     public float getScore() {
43         return score;
44    }
45     public void setScore(float score) {
46         this.score = score;
47    }
48 }

1 package com.lang;
 2 
 3 public final class System {
 4     //System 類(lei)不能被實例(li)化(hua)。 
 5     private System() {}
 6     //在 System 類提供(gong)的設施中(zhong)，有標(biao)準輸入、標(biao)準輸出和錯誤輸出流；對外部定義(yi)的屬性
 7     //和環境變量(liang)的(de)(de)訪問；加載文件和庫的(de)(de)方法；還有快(kuai)速復(fu)制數組(zu)的(de)(de)一(yi)部分的(de)(de)實用方法。
 8     /**
 9     * src and dest都必須是同類(lei)(lei)型或者可以進行轉換類(lei)(lei)型的(de)數組．
10     * @param      src      the source array.
11     * @param      srcPos   starting position in the source array.
12     * @param      dest     the destination array.
13     * @param      destPos  starting position in the destination data.
14     * @param      length   the number of array elements to be copied.
15      */
16     public static native void arraycopy(Object src, int srcPos, Object dest,
17             int destPos, int length);
18 }


1 package com.lang.reflect;
 2 
 3 public final class Array {
 4     private Array() {}
 5     
 6     //創建一個具有指定的組(zu)件類型和維度的新數組(zu)。
 7     public static Object newInstance(Class<?> componentType, int length)
 8             throws NegativeArraySizeException {
 9         return newArray(componentType, length);
10    }
11 
12     private static native Object newArray(Class componentType, int length)
13             throws NegativeArraySizeException;
14 }

1 List<string> uniqueKeyList = new ArrayList<string>();  
2 //......  
3 if (uniqueKeyList.contains(uniqueKey)) {  
4                    continue;  
  }

7public int indexOf(Object elem) {  
8    if (elem == null) {  
9        for (int i = 0; i < size; i++)  
10        if (elementData[i]==null)  
11            return i;  
12    } else {  
13        for (int i = 0; i < size; i++)  
14        if (elem.equals(elementData[i]))  
15            return i;  
16    }  
17    return -1;  
18    }  

Set<string> uniqueKeySet = new HashSet<string>();  
//......  
if (uniqueKeySet.contains(uniqueKey)) {  
                    continue;  
} 

public boolean contains(Object o) {  
   return map.containsKey(o);  
}