计数排序(八)

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

1. 动图演示

动图演示

2. JavaScript 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;

for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}

for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}

return arr;
}

3. Python 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr

4. Go 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func countingSort(arr []int, maxValue int) []int {
bucketLen := maxValue + 1
bucket := make([]int, bucketLen) // 初始为0的数组

sortedIndex := 0
length := len(arr)

for i := 0; i < length; i++ {
bucket[arr[i]] += 1
}

for j := 0; j < bucketLen; j++ {
for bucket[j] > 0 {
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
}
}

return arr
}

5. java 代码实现

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
public static void main(String[] args) throws Exception {  
int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 6, 1, 0 };

System.out.println("Before sort:");
ArrayUtils.printArray(array);

countingSort(array, 9);

System.out.println("After sort:");
ArrayUtils.printArray(array);
}

public static void countingSort(int[] array, int range) throws Exception {
if (range <= 0) {
throw new Exception("range can't be negative or zero.");
}

if (array.length <= 1) {
return;
}

int[] countArray = new int[range + 1];
for (int i = 0; i < array.length; i++) {
int value = array[i];
if (value < 0 || value > range) {
throw new Exception("array element overflow range.");
}
countArray[value] += 1;
}

for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}

int[] temp = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
int value = array[i];
int position = countArray[value] - 1;

temp[position] = value;
countArray[value] -= 1;
}

for (int i = 0; i < array.length; i++) {
array[i] = temp[i];
}
}

作者:搜云库技术团队
出处:https://www.souyunku.com
首发微信公众号:搜云库技术团队,微信号ID:souyunku
版权归原创作者所有,任何形式转载请联系作者

# sort

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×