计数排序和桶排序——python和javascript实现

ゝ一世哀愁。 2023-01-16 15:27 59阅读 0赞

# 计数排序 #

## python版 ##

### 不稳定计数排序 ###

# 不稳定计数排序
    def count_sort(arr):
    	max,min = findMaxAndMin(arr)
    	space = max - min
    	countArr = [0] * (space+1)
    	resultArr = []
    	
    	# 计数
    	for num in arr:
    		for j in range(0,space+1):
    			if num == j:
    				countArr[j]+=1
    	# 排序 
    	for i in range(0,len(countArr)):
    		if countArr[i] > 0:
    			tmp = countArr[i]
    			while tmp:
    				resultArr.append(min+i)
    				tmp-=1
    
    	return resultArr
    
    
    
    def findMaxAndMin(arr=[]):
    	max = arr[0]
    	min = arr[0]
    	for i in range(1, len(arr)):
    		if arr[i] > max:
    			max = arr[i]
    		if arr[i] < min:
    			min = arr[i] 
    	return max,min
    
    
    my_array = list([4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10])
    print(count_sort(my_array))

### 稳定计数排序 ###

# 稳定计数排序
    def count_sort(arr):
    	max,min = findMaxAndMin(arr)
    	space = max - min
    	countArr = [0] * (space+1)
    	resultArr = [0] * (space+1)
    	
    	# 计数
    	for num in arr:
    		for j in range(0,space+1):
    			if num == j:
    				countArr[j]+=1
    	# 累加
    	acculate = 0
    	for i in range(0,space+1):
    		acculate+=countArr[i]
    		resultArr[i] += acculate
    
    	sorted_array = [0] * len(arr)
    
    	# 按序
    	for i in range(len(arr)-1,-1,-1):
    		sorted_array[resultArr[arr[i]-min]-1] = arr[i]
    		resultArr[arr[i]-min] -= 1
    
    	return sorted_array
    
    
    
    def findMaxAndMin(arr=[]):
    	max = arr[0]
    	min = arr[0]
    	for i in range(1, len(arr)):
    		if arr[i] > max:
    			max = arr[i]
    		if arr[i] < min:
    			min = arr[i] 
    	return max,min
    
    
    my_array = list([4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10])
    print(count_sort(my_array))

## javascript版 ##

### 不稳定排序 ###

// 计数排序
    // 不稳定排序
    function count_sort(arr=[]){ 
    	const obj = getMaxAndMin(arr);
    	const max = obj.max || 0;
    	const min = obj.min || 0;
    	const space = max - min;
    	let countArr = [];
    	let result = [];
    	countArr.length = space + 1;
    	countArr.fill(0);
    
    	for(let i=0;i<=arr.length-1;i++){ 
    		for(let j=0;j<=countArr.length-1;j++){ 
    			if(arr[i] === j) countArr[j]++
    		}
    	}
    
    	for(let i=0;i<=countArr.length-1;i++){ 
    		if(countArr[i] > 0){ 
    			let tmp = countArr[i]
    			while(tmp > 0){ 
    				result.push(min+i)
    				tmp--;
    			}
    		}
    	}
    	return result;
    }
    
    function getMaxAndMin(arr=[]){ 
    	let max = min = space = 0;
    	arr.forEach(item => { 
    		if(item > max) max = item;
    		if(item < min) min = item;
    	})
    	return { max,min};
    }
    
    let arr = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10];
    count_sort(arr)

### 稳定排序 ###

// 计数排序
    // 稳定排序
    function count_sort(arr=[]){ 
    	const obj = getMaxAndMin(arr);
    	const max = obj.max || 0;
    	const min = obj.min || 0;
    	const space = max - min;
    	let countArr = [];
    	let accArr = [];
    	let result = [];
    	countArr.length = space + 1;
    	countArr.fill(0);
    
    	for(let i=0;i<=arr.length-1;i++){ 
    		for(let j=0;j<=countArr.length-1;j++){ 
    			if(arr[i] === j) countArr[j]++
    		}
    	}
    
    	let accumulat = 0;
    	for(let i=0;i<=countArr.length-1;i++){ 
    		accumulat+=countArr[i];
    		accArr.push(accumulat);
    	}
    
    	for(let i=0;i<=arr.length-1;i++){ 
    		result[accArr[arr[i]-min]-1] = arr[i];
    		accArr[arr[i]-min]--;
    	}
    
    	return result;
    }
    
    function getMaxAndMin(arr=[]){ 
    	let max = min = space = 0;
    	arr.forEach(item => { 
    		if(item > max) max = item;
    		if(item < min) min = item;
    	})
    	return { max,min};
    }
    
    let arr = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10];
    count_sort(arr)

# 桶排序 #

## python版 ##

import math
    
    # 桶排序
    def bucket_sort(arr):
    	max,min = findMaxAndMin(arr)
    	space = max - min
    	bucket_num = len(arr);
    	bucket_arr = [[]*bucket_num for _ in range(bucket_num)]
    	bucket_range = space / bucket_num
    	result = []
    
    	# 元素入桶
    	for i in range(0,len(arr)):
    		res = arr[i]-min / bucket_range
    		bucket_index = math.ceil(res) 
    		bucket_arr[bucket_index].append(arr[i])
    	
    	# 桶内稳定排序
    	for arr in bucket_arr:
    		unilateralQuick(0,len(arr)-1,arr)
    		for i in arr:
    			result.append(i)
    	return result
    
    
    def findMaxAndMin(arr=[]):
    	max = arr[0]
    	min = arr[0]
    	for i in range(1, len(arr)):
    		if arr[i] > max:
    			max = arr[i]
    		if arr[i] < min:
    			min = arr[i] 
    	return max,min
    
    # 单指针快速排序
    def unilateralQuick(startIndex, endIndex, arr):
        if startIndex >= endIndex:
            return
    
        base = findBase(startIndex, endIndex, arr)
        unilateralQuick(startIndex, base-1, arr)
        unilateralQuick(base+1, endIndex, arr)
    
    def findBase(startIndex,endIndex,arr):
        baseNumber = arr[startIndex]
        mark = startIndex
    
        for i in range(startIndex+1, endIndex+1):
            if arr[i] < baseNumber:
                mark += 1
                arr[i], arr[mark] = arr[mark], arr[i]
    
        arr[startIndex], arr[mark] = arr[mark], arr[startIndex]
        return mark
    
    arr = [3.57,4.23,1.36,8.77,1.11,6.78,1.12,1.13,1.37,2.56,3.57]
    
    print(bucket_sort(arr))

## javascript版 ##

// 桶排序
    function bucket_sort(arr){ 
    	const obj = getMaxAndMin(arr);
    	const max = obj.max;
    	const min = obj.min;
    	const space = max - min;
    	const bucket_num = arr.length;
    	const bucket_range = space / bucket_num;
    	let bucket_arr = [];
    	let result = [];
    	bucket_arr.length = bucket_num + 1;
    	for(let i=0;i<=bucket_arr.length-1;i++){ 
    		bucket_arr[i] = [];
    	}
    
    	//元素入桶
    	for(let i=0;i<=arr.length-1;i++){ 
    		res = arr[i] - min / bucket_range;
    		bucket_index = Math.ceil(res);
    		bucket_arr[bucket_index].push(arr[i])
    	}
    
    	// 桶内快速排序
    	for(let i=0;i<=bucket_arr.length-1;i++){ 
    		if(bucket_arr[i].length > 0){ 
    			UnilateralQuick(0,bucket_arr[i].length-1,bucket_arr[i])
    			for(let j=0;j<=bucket_arr[i].length-1;j++){ 
    				result.push(bucket_arr[i][j])
    			}
    		}
    	}
    
    
    	return result;
    
    }
    
    function getMaxAndMin(arr=[]){ 
    	let max = min = space = 0;
    	arr.forEach(item => { 
    		if(item > max) max = item;
    		if(item < min) min = item;
    	})
    	return { max,min};
    }
    
    // 单指针快速排序
    function UnilateralQuick(startIndex,endIndex,arr){ 
    	if(startIndex >= endIndex){ 
    		return;
    	}
    	base = findBase(startIndex,endIndex,arr);
    	UnilateralQuick(startIndex,base-1,arr);
    	UnilateralQuick(base+1,endIndex,arr)
    }
    
    function findBase(startIndex,endIndex,arr){ 
    	let mark = startIndex;
    	let baseNumber = arr[startIndex];
    
    	for(let i=startIndex+1;i<=endIndex;i++){ 
    		if(arr[i] < baseNumber){ 
    			mark++;
    			let tmp = arr[i];
    			arr[i] = arr[mark];
    			arr[mark] = tmp;
    		}
    	}
    
    	arr[startIndex] = arr[mark];
    	arr[mark] = baseNumber;
    
    	return mark;
    }
    
    
    arr = [3.57,4.23,1.36,8.77,1.11,6.78,1.12,1.13,1.37,2.56,3.57]
    
    bucket_sort(arr)