排序算法-计数排序

孤峰孤峰家 2023-07-16 11人阅读

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

1. 动图演示

2. JavaScript 代码实现

function countingSort(arr, **xValue) { 
var bucket = new Array(**xValue+1), 
sortedIndex = 0; 
arrLen = arr.length, 
bucketLen = **xValue + 1; 

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

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

return arr; 
}

3. Python 代码实现
def countingSort(arr, **xValue): bucketLen = **xValue+1 bucket = [0]*bucketLen sortedIndex =0 arrLen = len(arr) for i in range(arrLen): if not bucket[arr]: bucket[arr]=0 bucket[arr]+=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, **xValue int) []int { bucketLen := **xValue + 1 bucket := **ke([]int, bucketLen) // 初始为0的数组 sortedIndex := 0 length := len(arr) for i := 0; i < length; i++ { bucket[arr] += 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 **xValue = getMaxValue(arr); return countingSort(arr, **xValue); } private int[] countingSort(int[] arr, int **xValue) { int bucketLen = **xValue + 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 **xValue = arr[0]; for (int value : arr) { if (**xValue < value) { **xValue = value; } } return **xValue; } }
全选代码
复制

6. PHP 代码实现
function countingSort($arr, $**xValue = null) { if ($**xValue === null) { $**xValue = **x($arr); } for ($m = 0; $m < $**xValue + 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){ for($j = 0; $j < $len; $j++){ $arr[$sortedIndex++] = $key; } } } return $arr; }
全选代码
复制

文档下载

排序算法-计数排序.doc

很赞哦！ (23)

转载：感谢您阅览，转载请注明文章出处“来源从小爱孤峰知识网：一个分享知识和生活随笔记录的知识小站”。

链接：排序算法-计数排序http://www.gufeng7.com/niaolang/552.html

联系：如果侵犯了你的权益请来信告知我们删除。邮箱：119882116@qq.com