为什么这种循环排序有错误？

Question

众所周知的问题：

给出n范围从1到n的数组数。对原位O（1）空间进行排序。

Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

我的解决方法是

  public static void sort(int[] nums) {
    int n = nums.length;

    for(int i = 0; i < n; i++){
      if(nums[nums[i] -1] != nums[i]){  // if I use while here it works.
        int j = nums[i] -1;
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
      }
   }
 }    

但是此错误如下。

Input: [1, 5, 6, 4, 3, 2]
Wrong output: [1, 3, 2, 4, 5, 6]

如果我在for循环中使用while（而不是if），则可以使用。不知道如果我在if循环中使用for语句，为什么会有bug。

有人可以澄清原因吗？

Answer 1

如果您不想Arrays.sort(nums)，这应该可以工作>

int[] nums= new int[]{ 1, 5, 6, 4, 3, 2 }; 
int n = nums.length;

for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
    if (nums[i] < nums[j]) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
 }
}
for (int i = 0; i < n; i++){
  System.out.println(nums[i]);
}

输出

[1, 2, 3, 4, 5, 6]

Answer 2

这是带有注释的代码，用于说明发生了什么。每次交换都会放置至少一个元素。这是按等级排序的，因为a [i] -1包含它应存储在的位置，而不是一个排序索引数组，排序索引数组应包含应该读取的位置元素（例如，排序索引+ 1表示{3，1，5，4，2} {将是{2 5 1 4 3}索引+1到{1 2 3 4 5}，但这将需要第二个数组来包含排序的索引）。空间复杂度为O（1）。时间复杂度为O（n）。