题目标题

如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)

难度:初级

算法 数据结构
参考解析
  1. #include <iostream>
  2. using namespace std;
  3. void SuperSort(int *arr, int n);
  4. int main() {
  5. int n;
  6. cin>>n;
  7. int i = 0;
  8. int *arr = new int[n];
  9. for(i=0;i<n;i++)
  10. cin>>arr[i];
  11. SuperSort(arr,n);
  12. //前面几个实验都老是忘了delete 这个很不好,还是要铭记在心,尤其我是那么那么的珍惜内存啊
  13. delete arr;
  14. return 0;
  15. }
  16. void SuperSort(int *arr, int n){
  17. int hashTable[65535];
  18. int i = 0;
  19. //申请空间初始化
  20. for(i=0;i<65535;i++)
  21. hashTable[i]=0;
  22. //排序
  23. for(i=0;i<n;i++)
  24. hashTable[arr[i]]++;
  25. //结果
  26. for(i=0;i<65535;i++){
  27. if(hashTable[i] != 0){
  28. cout<<i<<" ";
  29. hashTable[i--]--;
  30. }
  31. }
  32. }