Java中Arrays的sort方法汇总.docx

1Java中Arrays的sort方法 数组的排序，Java自带的Arrays类的sort方法主要内容包括插入排序结合分治排序两种排序算法在里面。先分别介绍一下两种排序方式：第一种：通过分治法实现的并归排序。12345678910111213141516171819202122SuppressWarnings(unchecked )public static void mergeSort(Comparable src , Comparable dest, int low, int high) if (high - low = 1) return;if (high - low = 2) if (pareTo(desthigh - 1) 0) swap(dest, low, high - 1);return;int mid = (low+high) 1;mergeSort(dest, src , low, mid);mergeSort(dest, src , mid, high);for (int i = low, p = low, q = mid; i high; i+) if (q = high| (p != mid & src pareTo(srcq) 0) desti = srcp+; else desti = srcq+;第二种：插入排序。123456789private static void InsertionSort(Comparable src,Comparable dest,int low,int high)for(int i=low;ilow;j-)if(pareTo(destj-1) 0) swap(dest, low, high - 1);return;int mid = (low+high) 1;mergeSort(dest, src, low, mid);mergeSort(dest, src, mid, high);for (int i = low, p = low, q = mid; i high; i+) if (q = high| (p != mid & pareTo(srcq) 0) desti = srcp+; else desti = srcq+;SuppressWarnings( unused , unchecked )private static void InsertionSort(Comparable src, Comparable dest,int low, int high) for (int i = low; i low; j-) if (pareTo(destj - 1) 0) swap(dest, j, j - 1);private static String getStrings(int length) Random random = new Random();String strs = new Stringlength;for (int i = 0; i length; i+) int temp = random.nextInt(999);strsi = Integer. toString(temp);return strs;private static void swap (Object x, int a, int b) Object t = xa;xa = xb;xb = t;public static void main(String args) String strs = getStrings(10);String aux = strs.clone();long begin = System.currentTimeMillis();mergeSort(strs, aux, 0, strs.length);System. out.println(System.currentTimeMillis() - begin);System. out.println(Arrays.asList(strs);System. out.println(Arrays.asList(aux);将插入排序放入并归排序中：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566public class ArraysSort /* 排序的代码* param src* param dest* param low* param high*/SuppressWarnings(unchecked )public static void mergeSort(Comparable src, Comparable dest, int low, int high) if (high - low 7) for (int i = low; i low; j-) if (pareTo(destj - 1) 1;mergeSort(dest, src, low, mid);mergeSort(dest, src, mid, high);for (int i = low, p = low, q = mid; i high; i+) if (q = high| (p != mid & pareTo(srcq) 0) desti = srcp+; else desti = srcq+;/* 数组置换位置* param x* param a* param b*/private static void swap(Object x, int a, int b) Object t = xa;xa = xb;xb = t;/* 测试的方法* param length* return*/private static String getStrings(int length) Random random = new Random();String strs = new Stringlength;for (int i = 0; i length; i+) int temp = random.nextInt(999);strsi = Integer. toString(temp);return strs;public static void main(String args) String strs = getStrings(10);String aux = strs.clone();long begin = System.currentTimeMillis();mergeSort(strs, aux, 0, strs.length);System. out.println(System.currentTimeMillis() - begin);System. out.println(Arrays.asList(strs);System. out.println(Arrays.asList(aux);Arrays的sort方法如下：12345678910111213141516171819202122232425262728293031323334353637383940private static void mergeSort(Object src, Object dest, int low, int high, int off) int length = high - low;/ Insertion sort on smallest arraysif (length INSERTIONSORT_THRESHOLD) for (int i=low; ilow &( Comparable) destj-1).compareTo(destj)0; j-)swap(dest, j, j-1);return;/ Recursively sort halves of dest into srcint destLow = low;int destHigh = high;low += off;high += off;int mid = (low + high) 1;mergeSort(dest, src, low, mid, -off) ;mergeSort(dest, src, mid, high, -off) ;/ If list is already sorted, just copy from src to dest. This is an/ optimization that results in faster sorts for nearly ordered lists.if (Comparable)srcmid-1).compareTo(srcmid) = 0) System. arraycopy(src, low, dest, destLow, length);return;/ Merge sorted halves (now in src) into destfor(int i = destLow,