時間複雜度O(n)，空間複雜度O(1)的排序

貌似是個老題目，巧用下标。

題目描述：

有1,2,....一直到n的無序數組,求排序算法,并且要求時間複雜度為O(n),空間複雜度O(1),使用交換,而且一次隻能交換兩個數.

考慮到平時接觸最多的幾種排序，時間複雜度都沒有O(n)的，看看題目，它也有它的特殊的地方，

待排序的數組為1。。。n，可用下标處理。具體如下：

void MySort(int a[], int n)
{
	int i, j, t;
	for (i = 1; i < n ; i++)
	{
		j = i;//j可以不用的
		while (a[j] != j)
		{
			t = a[a[j]];
			a[a[j]] = a[j];
			a[j] = t;
		}
	}
}
           

重點就是a[j]表示的是數，同時也可以表示下标。

i需要從1開始循環，因為要排序的是從1開始的。

體會一下。