学步园

题目：一个N元数组，乱序存放0~N-1的数字，只允许同数字0所在位置交换，排序整个数组

思路：首先找出0所在的位置，将0交换到第0位。从第1位开始依次判断后续的数字x是否放在正确位置，若位置正确，进行后续检查；若位置不正确，将该数字x，该数字x要放位置的数字y及0，三数字进行交换，此后，x换到了正确位置，继续检查y是否正确，直到正确为止。

分析：时间复杂度O(N)，空间复杂度O(1)

/*
 * 一个N元数组，乱序存放0~N-1的数字，
 * 只允许同数字0所在位置交换，
 * 排序整个数组
 *
 */
#include <stdio.h>

template <typename T>
void swap(T &a, T &b)
{
	T c = a; a = b; b = c;
}

void sort_N(int array[], int N)
{
	int indexOf0 = 0;
	while (array[indexOf0] != 0)
		++ indexOf0;
	swap(array[0], array[indexOf0]); // array[0] == 0
	for (int i = 1; i < N;)
	{
		if (array[i] != i)
		{
			int k = array[i];
			swap(array[k], array[0]); // array[k] == 0
			swap(array[k], array[i]); // array[i] == 0
			swap(array[i], array[0]); // array[0] == 0
		}
		else 
			++ i;
	}
}

PS：Google，2013，校招，笔试