实现一个排序算法，对0~n-1范围内的n个不重复的无序数组进行排序，时间复杂度为O(n)，空间复杂度为O(1)。

题目：实现一个排序算法，对0~n-1范围内的n个不重复的无序数组进行排序，时间复杂度为O(n)，空间复杂度为O(1)。

思想：从头到尾扫描这个数组中的每个数字，当扫描到下标为i的数字是，首先比较这个数字（假设为m）是不是等于i，如果等于继续下去；如果不等于则就和第m个位置的数字交换，依次重复下去，直到循环结束。

代码如下：

#include <iostream>
#include <vector>
using namespace std;

void Mysort(vector<int> & arr) {
	int len = arr.size();
	if (len <= 1)
		return;
	for (int i = 0; i < len; i++) {
		while (arr[i] != i) {
			swap(arr[i], arr[arr[i]]);			//交换
		}
	}
}

int main()
{
	vector<int> arr = { 4,6,3,1,5,2,7,0 };
	Mysort(arr);
	for (auto x : arr)
		cout << x << " ";
	return 0;
}

运行结果如下：