问题描述： int a[] = {15，14，15，18，16，17，14，17，15，15}，要求对数组a进行排序，要求时间复杂度为O(N) 。
#include<iostream> #include<stdlib.h> using namespace std; void Sort(int arr[], size_t size) { //先找出最大值和最小值 int max = arr[0]; int min = arr[0]; for (size_t idx = 1; idx < size; ++idx) { if (max < arr[idx]) max = arr[idx]; if (min > arr[idx]) min = arr[idx]; } size_t new_size = max - min + 1; //大小为new_size的count数组记录数据出现的次数，count数组的下标+min==数据 int *count = new int[new_size]; memset(count, 0, sizeof(int)*new_size); for (size_t idx = 0; idx < size; ++idx) { count[arr[idx] - min]++; } //再根据count中数据出现次数将数据排列在arr中 size_t pos = 0; for (size_t idx = 0; idx < new_size; idx++) { while (count[idx]>0) { arr[pos] = idx + min; pos++; count[idx]--; } } delete[] count; } int main() { int arr[11] = { 15,14,15,18,16,17,14,17,15,15}; Sort(arr, sizeof(arr)/sizeof(arr[0])); system("pause"); return 0; }