有1，2，……一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂度为O(1)，使用交换，而且一次只能交换两个数。
这个是以前看到的算法题，题目不难。但是要求比较多，排序算法中，时间复杂度为O(n)就是基数排序了。
现在介绍两种解法：
解法一：用数组特性——下标实现交换
扫描数组，每次arr[i],arr[arr[i]-1]交换，如果arr[i]=i+1，则什么都不做。这样交换一次保证一个数字被放到它应该被放置的位置上。最后数组有序。
#include <vector>
#include <iostream>
using namespace std; void swap(int& a, int& b){
a^=b;
b^=a;
a^=b;
}
vector<int>& Sort(vector<int>& vec1){
if(vec1.size()==)
return vec1;
for(int i=;i<vec1.size();){
if(vec1[i]==i+)
i++;
else swap(vec1[i],vec1[vec1[i]-]);
}
return vec1;
}
int main(){
int arr[]={,,,,,,,,};
vector<int> vec2(arr,arr+);
Sort(vec2);
for(int i=;i<vec2.size();i++)
cout<<vec2[i]<<" ";
return ;
}
上面的题目是每个数字只出现一次，如果不限制出现的次数，要求时间复杂度是O(n)，空间复杂度为O(1)又该怎么做，给出数字的最大范围假设为65536。
这个题用桶排序应该可以做。
解法二：利用count[65536]（和n无关，空间复杂度为O(1)）数组记录出现的次数
那么假设有下面这些数字：
100
200
300
119
6
...
那么对于每个这个数字，都做在count中记录一下：
100 => count[100]++
200 => count[200]++
300 => count[300]++
119 => count[119]++
0 => count[0]++
6 => count[6]++
最后，遍历一边所有这些数字就可得到0~65535每个数字的个数（在count数组中），然后再顺序遍历count数组，count[n] = m，则输出m个n，（比如说有count[3] = 2, 那么说明有2个数字3），依次输出，最后可得结果。