编辑代码

#include <iostream>
using namespace std ;

void findMinMax(int arr[], int len, int& min, int&max) {
	min = arr[0];
	max = arr[0];
	
	for(int i = 1; i < len; ++i) {
		if (arr[i] < min) {
			min = arr[i];
		}
		else if (arr[i] > max) {
			max = arr[i];
		}
	} 
}



void lineCountSort(int arr[], int len, int orderedArr[]) {
	int min, max;
	findMinMax(arr, len, min, max);
	
	int countLen = max - min + 1;
	
	//计数的数组
	int *count = new int(countLen);
	
	for (int i = 0; i < countLen; ++i) {
		count[i] = 0;
	} 
	
	//统计比i对应的元素个数
	for (int i = 0; i < len; ++i) {
	     ++count[arr[i] - min];
	} 
	//printArray(count, countLen);
	
	//计算出小于等于i对应元素的元素的个数 
	for (int i = 1; i < countLen; ++i ){
		count[i] = count[i] + count[i-1];
	}
	
	//利用计数的值进行排序
	for (int i = len-1; i >= 0; --i) {
		
		orderedArr[--count[arr[i] - min]] = arr[i];
		
	} 
	 
}

void printArray(int* arr, int len) {
	for (int i = 0; i < len; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl; 	
}

int main() {
	int arr[] = {62, 47, 84, 96, 62, 47, 96, 96};
	int orderedArr[8];
	
	printArray(arr, 8);
	lineCountSort(arr, 8, orderedArr);
	printArray(orderedArr, 8);
	
	return 0;
}