计数排序
计算待排序数组的最大值和最小值
计数数组位最大值到最小值的长度
循环待排序数组，计数并按照值减最小是的下标放入计数数组
循环计数数组，计算每个值前面的个数和
再次循环待排序数组，找到计数小标的值，即为当前的排位，同步给排位加一（加一处理相当的情况）
时间复杂度为O(n+k)，k为数组区间范围，由此可见该方法适用于区间比较短的排序，空间复杂度O(n+k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| private void countingSort(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int e : arr) {
if (e < min) min = e;
if (e > max) max = e;
}
int length = max - min + 1;
int[] tmp = new int[length];
for (int e : arr) {
tmp[e - min]++;
}
int preCount = 0;
for (int i = 0; i < tmp.length; i++) {
int pt = tmp[i];
tmp[i] = preCount;
preCount += pt;
}
int[] tmpArr = new int[arr.length];
for (int e : arr) {
tmpArr[tmp[e - min]] = e;
tmp[e - min]++;
}
for (int i = 0; i < tmpArr.length; i++) {
arr[i] = tmpArr[i];
}
}
|
概率
“猜数字”游戏：一方从 [1, 100][1,100] 中随机选取一个数字，另一方来猜。每次猜测都会得到「高了」或者「低了」的回答。怎样才能以最少的次数猜中呢？
二分。
二分算法能够保证每次都排除一半的数字。每次猜测不会出现惊喜（一次排除了多于一半的数字），也不会出现悲伤（一次只排除了少于一半的数字），因为答案的每一个分支都是等概率的，所以它在最差的情况下表现是最好的，猜测的一方在logn次以内必然能够猜中。
基于比较的排序算法与“猜数字”是类似的，每次比较，我们只能得到 a > ba>b 或者 a ≤ ba≤b 两种结果，如果我们把数组的全排列比作一块区域，那么每次比较都只能将这块区域分成两份，也就是说每次比较最多排除掉1/2的可能性。
计数排序算法，计数排序时申请了长度为 k 的计数数组，在遍历每一个数字时，这个数字落在计数数组中的可能性共有 k 种，但通过数字本身的大小属性，一次即可把它放到正确的位置上。相当于一次排除了 (k - 1)/k(k−1)/k 种可能性。这就是计数排序算法比基于比较的排序算法更快的根本原因。
基数排序
找出最大值
计算最大值的长度，需根据最大值的长度计算基数，并对基数做比较
从尾到头或从头到尾的方式，一位一位比较，一位一位比较的时候使用计数排序，因为每一位的数字是0-9，为了处理负数，使用从-9-9的方式（如果使用0-9，负数加变正数容易引起int越界）
人排序的时候从头到尾更快，计算机排序的话从尾到头更容易
基数排序是稳定的排序
基数排序的时间复杂度为 O(d(n + k))O(d(n+k))(d 表示最长数字的位数，k 表示每个基数可能的取值范围大小)。空间复杂度为 O(n + k)O(n+k)（k 表示每个基数可能的取值范围大小）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
private int[] radixSort(int[] arr) {
int max = 0;
int min = 0;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) max = arr[i];
if (min > arr[i]) min = arr[i];
}
int maxDigitLengthTmp = 0;
while (max != 0) {
maxDigitLengthTmp++;
max /= 10;
}
int maxDigitLength = maxDigitLengthTmp;
maxDigitLengthTmp = 0;
while (min != 0) {
maxDigitLengthTmp++;
min /= 10;
}
maxDigitLength = Math.max(maxDigitLength, maxDigitLengthTmp);
int[] countingArr = null;
int[] arrTmp = new int[arr.length];
int dev = 1;
while (maxDigitLength-- > 0) {
countingArr = new int[19];
for (int i = 0; i < arr.length; i++) {
countingArr[arr[i] / dev % 10 + 9]++;
}
int preCount = 0;
for (int i = 0; i < countingArr.length; i++) {
int tmp = countingArr[i];
countingArr[i] = preCount;
preCount += tmp;
}
for (int i = 0; i < arr.length; i++) {
arrTmp[countingArr[arr[i] / dev % 10 + 9]] = arr[i];
countingArr[arr[i] / dev % 10 + 9]++;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = arrTmp[i];
}
dev *= 10;
}
return arr;
}
|
桶排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| private void bucketSort(int[] arr) {
if (arr == null || arr.length <= 0) return;
int min = arr[0];
int max = arr[0];
for (int e : arr) {
if (e > max) max = e;
if (e < min) min = e;
}
int bucketCount = 1;
if (arr.length > 10) {
bucketCount = arr.length / 10;
}
double gap = ((double) (max - min) / (bucketCount - 1));
List<Integer>[] bucketTmp = new LinkedList[bucketCount];
for (int e : arr) {
List<Integer> list = bucketTmp[(int) ((e - min) / gap)];
if (list == null) {
bucketTmp[(int) ((e - min) / gap)] = new LinkedList();
list = bucketTmp[(int) ((e - min) / gap)];
}
list.add(e);
}
int index = 0;
for (List<Integer> list : bucketTmp) {
if (list == null || list.size() <= 0) continue;
int[] tmp = new int[list.size()];
for (int n = 0; n < list.size(); n++) {
tmp[n] = list.get(n);
}
radixSort(tmp);
for (int m = 0; m < tmp.length; m++) {
arr[index++] = tmp[m];
}
}
}
|