题目
给定一个长度为N的整型数组arr，其中有N个互不相等的自然数1~N，请实现arr的排序，但是不要把下标0~N-1位置上的数通过直接赋值的方式替换成1~N。
解答
arr在调整之后应该事下标从0到N-1的位置上依次放着1~N，即arr[index] = index + 1。
1、从左到右遍历arr，假设当前遍历到i位置。
2、如果arr[i] ==i+1,说明当前的位置不需要调整，继续遍历下一个位置。
3、如果arr[i] != i+1,说明此时i位置的数arr[i]不应该放在i位置上，接下来将进行跳的过程。
举例说明，比如[1,2,5,3,4],假设遍历到位置2，也就是5这个数。5应该放在位置4上，所以把5放过去，数组变成[1,2,5,3,5]。同时，4这个数是被5替下来的数，应该放在位置3，所以把4放过去，数组变成[1,2,5,4,5]。同时3这个数是被4替下来的数，应该放在位置2，所以把3放过去，数组变成[1,2,3,4,5]。当跳了一圈回到原来位置后，会发现此时arr[i]==i+1,继续遍历下一个位置。
public void sort1(int[] arr){int tmp = 0;int next = 0;for(int i = 0; i!= arr.length;i++){tmp = arr[i];while(arr[i] != i + 1){next = arr[tmp - 1];arr[tmp - 1 ] = tmp;tmp = next;}}
}1、从左到右遍历arr，假设当前遍历到i位置。
2、如果arr[i] == i + 1,说明当前的位置不需要调整，继续遍历下一个位置。
3、如果arr[i] != i + 1,说明此时i位置的数arr[i]不应该放在i位置上，接下来将在i位置进行交换过程。
比如[1,2,5,3,4],假设遍历到位置2，也就是5这个数。5应该放在位置4上，所以位置4上的数4和5交换，数组变成[1,2,4,3,5]。但此时还是arr[2]!=3,4这个数应该放在位置3上，所以3和4交换，数组变成[1,2,3,4,5]。此时arr[2] == 3,遍历下一个位置。
public void sort2(int[] arr){int tmp = 0;for(int i = 0;i<arr.length;i++){while(arr[i] != i + 1){tmp = arr[i];arr[i] = arr[arr[i] - 1];arr[arr[i] - 1] = tmp;}}
}public void sort3(int[] arr){int tmp = 0;for(int i = 0;i<arr.length;i++){while(arr[i] != i + 1){tmp = arr[arr[i] - 1];arr[arr[i] - 1]= arr[i];arr[i] = tmp;}}
}
)
)
