常见算法时间复杂度
O(1): 表示算法的运行时间为常量
O(n): 表示该算法是线性算法
O(㏒2 n):二分查找算法
O(n㏒2 n):快排，合并排序
O(n2 ):对数组进行排序的各种简单算法，例如直接插入排序的算法。
O(n3 ):做两个n阶矩阵的乘法运算
O(2n ):求具有n个元素集合的所有子集的算法
O(n!): 求具有N个元素的全排列的算法
优<---------------------------<劣
O(1)<O(㏒2 n)<O(n)< O(n2 )<O(2n )
时间复杂度按数量级递增排列依次为：
常数阶O(1)、对数阶O(log2 n)、线性阶O(n)、线性对数阶O(nlog2 n)、平方阶O(n2)、立方阶O(n3)、……k次方阶O(nk)、指数阶O(2n
)。
排序
排序算法复杂度
|
類別
|
排序法
|
平均時間
|
最差狀況
|
穩定度
|
|
|
內部
|
氣泡排序
|
Bubble
|
O(n2)
|
O(n2)
|
不穩定
|
|
內部
|
插入排序
|
Insertion
|
O(n2)
|
O(n2)
|
穩定
|
|
內部
|
選擇排序
|
Selection
|
O(n2)
|
O(n2)
|
穩定
|
|
內部
|
謝爾排序
|
Shell
|
O(nlogn)
|
O(ns)1<S<2
|
不穩定
|
|
內部
|
快速排序
|
Quick
|
O(nlogn)
|
O(n2)
|
不穩定
|
|
內部
|
累堆排序
|
Heap
|
O(nlogn)
|
O(nlogn)
|
不穩定
|
|
內部
|
二元排序
|
Binary tree
|
O(nlogn)
|
O(n2)
|
不一定
|
|
外部
|
合併排序
|
Merge
|
O(nlogn)
|
O(nlogn)
|
穩定
|
各种排序算法实现：http://blog.csdn.net/ajian005/article/details/8162399
Java Arrays中提供了对所有类型的排序。其中主要分为Primitive(8种基本类型)和Object两大类。
基本类型：采用调优的快速排序；
对象类型：采用改进的归并排序。
一、对于基本类型源码分析如下（以int[]为例）：
Java对Primitive（int，float等原型数据）数组采用快速排序，对Object对象数组采用归并排序。对这一区别，sun在<<The Java Tutorial>>中做出的解释如下：
The sort operation uses a slightly optimized merge sort algorithm that is fast and stable:
* Fast: It is guaranteed to run in n log(n) time and runs substantially faster on nearly sorted lists. Empirical tests showed it to be as fast as a highly optimized quicksort. A quicksort is generally considered to be faster than a merge sort but isn't
stable and doesn't guarantee n log(n) performance.
* Stable: It doesn't reorder equal elements. This is important if you sort the same list repeatedly on different attributes. If a user of a mail program sorts the inbox by mailing date and then sorts it by sender, the user naturally expects that the now-contiguous
list of messages from a given sender will (still) be sorted by mailing date. This is guaranteed only if the second sort was stable.
也就是说，优化的归并排序既快速（nlog(n)）又稳定。
对于对象的排序，稳定性很重要。比如成绩单，一开始可能是按人员的学号顺序排好了的，现在让我们用成绩排，那么你应该保证，本来张三在李四前面，即使他们成绩相同，张三不能跑到李四的后面去。
而快速排序是不稳定的，而且最坏情况下的时间复杂度是O(n^2)。
另外，对象数组中保存的只是对象的引用，这样多次移位并不会造成额外的开销，但是，对象数组对比较次数一般比较敏感，有可能对象的比较比单纯数的比较开销大很多。归并排序在这方面比快速排序做得更好，这也是选择它作为对象排序的一个重要原因之一。
排序优化：实现中快排和归并都采用递归方式，而在递归的底层，也就是待排序的数组长度小于7时，直接使用冒泡排序，而不再递归下去。
分析：长度为6的数组冒泡排序总比较次数最多也就1+2+3+4+5+6=21次，最好情况下只有6次比较。而快排或归并涉及到递归调用等的开销，其时间效率在n较小时劣势就凸显了，因此这里采用了冒泡排序，这也是对快速排序极重要的优化。
源码中的快速排序，主要做了以下几个方面的优化：
1）当待排序的数组中的元素个数较少时，源码中的阀值为7，采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)，但是当数组元素较少时，插入排序优于快速排序，因为这时快速排序的递归操作影响性能。
2）较好的选择了划分元（基准元素）。能够将数组分成大致两个相等的部分，避免出现最坏的情况。例如当数组有序的的情况下，选择第一个元素作为划分元，将使得算法的时间复杂度达到O(n^2).
源码中选择划分元的方法:
当数组大小为 size=7 时 ，取数组中间元素作为划分元。int n=m>>1;(此方法值得借鉴)
当数组大小 7<size<=40时，取首、中、末三个元素中间大小的元素作为划分元。
当数组大小 size>40 时 ，从待排数组中较均匀的选择9个元素，选出一个伪中数做为划分元。
3）根据划分元 v ，形成不变式 v* (<v)* (>v)* v*
普通的快速排序算法，经过一次划分后，将划分元排到素组较中间的位置，左边的元素小于划分元，右边的元素大于划分元，而没有将与划分元相等的元素放在其附近，这一点，在Arrays.sort()中得到了较大的优化。
举例：15、93、15、41、6、15、22、7、15、20
因 7<size<=40,所以在15、6、和20 中选择v = 15 作为划分元。
经过一次换分后： 15、15、7、6、41、20、22、93、15、15. 与划分元相等的元素都移到了素组的两边。
接下来将与划分元相等的元素移到数组中间来，形成：7、6、15、15、15、15、41、20、22、93.
最后递归对两个区间进行排序[7、6]和[41、20、22、93].
部分源代码（一）如下：
1 package com.util;
2
3 public class ArraysPrimitive {
4 private ArraysPrimitive() {}
5
6 /**
7 * 对指定的 int 型数组按数字升序进行排序。
8 */
9 public static void sort(int[] a) {
10 sort1(a, 0, a.length);
11 }
12
13 /**
14 * 对指定 int 型数组的指定范围按数字升序进行排序。
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 * 当待排序的数组中的元素个数小于 7 时，采用插入排序 。
24 *
25 * 尽管插入排序的时间复杂度为O(n^2),但是当数组元素较少时， 插入排序优于快速排序，因为这时快速排序的递归操作影响性能。
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 * 当待排序的数组中的元素个数大于 或等于7 时，采用快速排序 。
35 *
36 * Choose a partition element, v
37 * 选取一个划分元，V
38 *
39 * 较好的选择了划分元(基准元素)。能够将数组分成大致两个相等的部分，避免出现最坏的情况。例如当数组有序的的情况下，
40 * 选择第一个元素作为划分元，将使得算法的时间复杂度达到O(n^2).
41 */
42 // 当数组大小为size=7时 ，取数组中间元素作为划分元。
43 int m = off + (len >> 1);
44 // 当数组大小 7<size<=40时，取首、中、末 三个元素中间大小的元素作为划分元。
45 if (len > 7) {
46 int l = off;
47 int n = off + len - 1;
48 /*
49 * 当数组大小 size>40 时 ，从待排数组中较均匀的选择9个元素，
50 * 选出一个伪中数做为划分元。
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 // 取出中间大小的元素的位置。
59 m = med3(x, l, m, n); // Mid-size, med of 3
60 }
61
62 //得到划分元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 //结果：6,7,15,15,15,15,20,22,41,93,
13 }
14 }
二、对于Object类型源码分析如下：
部分源代码（二）如下：
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()，理解深表复制和浅表复制
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 * >>>：无符号右移运算符
49 * expression1 >>> expresion2：expression1的各个位向右移expression2
50 * 指定的位数。右移后左边空出的位数用0来填充。移出右边的位被丢弃。
51 * 例如：-14>>>2； 结果为：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; //成绩
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 类不能被实例化。
5 private System() {}
6 //在 System 类提供的设施中，有标准输入、标准输出和错误输出流；对外部定义的属性
7 //和环境变量的访问；加载文件和库的方法；还有快速复制数组的一部分的实用方法。
8 /**
9 * src and dest都必须是同类型或者可以进行转换类型的数组．
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 //创建一个具有指定的组件类型和维度的新数组。
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 }
查找
查找方法：
a )算法简单，适应面广，稳定算法
b) 平均查找长度比较大，当n比较大时，查找效率会很低，时间复杂度为O(n)
a)针对有序的序列表，不稳定算法
因此可以根据这样的结构，首先根据与根结点的对比，在确定往左子树或右子树查找，缩小查找范围。
a)二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
b) 平衡二叉树:棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树,查找时间的时间复杂度为O(log2n)
二分查找法： Arrays.binarySearch(int[] a, int key)
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
数组复制(基本类型，对象类型)
基本类型数组复制(如int[])
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
对象类型数组复制(对象类型)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
Arrays.copyOf()与System.arraycopy()的源码分析：
首先观察先System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)的实现方式：
- public static native void arraycopy(Object src, int srcPos,
- Object dest, int destPos,
- int length);
src - 源数组。
srcPos - 源数组中的起始位置。
dest - 目标数组。
destPos - 目标数据中的起始位置。
length - 要复制的数组元素的数量。
该方法是用了native关键字，调用的为C++编写的底层函数，可见其为JDK中的底层函数。
再来看看Arrays.copyOf();该方法对于不同的数据类型都有相应的方法重载。
- //非基本类型
- public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
- T[] copy = ((Object)newType == (Object)Object[].class)
- ? (T[]) new Object[newLength]
- : (T[]) Array.newInstance(newType.getComponentType(), newLength);
- System.arraycopy(original, 0, copy, 0,
- Math.min(original.length, newLength));
- return copy;
- }
- //基本数据类型
- public static int[] copyOf(int[] original, int newLength) {
- int[] copy = new int[newLength];
- System.arraycopy(original, 0, copy, 0,
- Math.min(original.length, newLength));
- return copy;
- }
original - 要复制的数组
newLength - 要返回的副本的长度
newType - 要返回的副本的类
观察其源代码发现copyOf()，在其内部创建了一个新的数组，然后调用arrayCopy()产生新的数组对象，返回出去。
总结：
1. copyOf()的实现是用的是arrayCopy();
2. arrayCopy()需要目标数组，对两个数组的内容进行可能不完全的合并操作。
3. copyOf()在内部新建一个数组，是用arrayCopy()将oldArray内容复制到newArray中去，并且长度为newLength。返回newArray;