題目
給定一個長度為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;}}
}
)
)
