920ab60 Apr 16, 2018
4 contributors

### Users who have contributed to this file

157 lines (124 sloc) 3.22 KB

# 计数排序

## 2. JavaScript 代码实现

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 代码实现

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 代码实现

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 代码实现

public class CountingSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

int maxValue = getMaxValue(arr);

return countingSort(arr, maxValue);
}

private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];

for (int value : arr) {
bucket[value]++;
}

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

private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}

}

## 6. PHP 代码实现

function countingSort(\$arr, \$maxValue = null)
{
if (\$maxValue === null) {
\$maxValue = max(\$arr);
}
for (\$m = 0; \$m < \$maxValue + 1; \$m++) {
\$bucket[] = null;
}

\$arrLen = count(\$arr);
for (\$i = 0; \$i < \$arrLen; \$i++) {
if (!array_key_exists(\$arr[\$i], \$bucket)) {
\$bucket[\$arr[\$i]] = 0;
}
\$bucket[\$arr[\$i]]++;
}

\$sortedIndex = 0;
foreach (\$bucket as \$key => \$len) {
if (\$len !== null) \$arr[\$sortedIndex++] = \$key;
}

return \$arr;
}
You can’t perform that action at this time.