本文旨在解析Java循环排序算法中一种常见的失效情况。通过对比错误代码和正确代码，详细分析了导致排序失败的原因，并提供了有效的解决方案。理解此问题有助于开发者更深入地掌握循环排序的原理，避免在实际应用中犯类似错误。
循环排序（Cyclic Sort）是一种用于排序包含从 1 到 N 的 N 个不同整数的数组的有效算法。其核心思想是将每个元素放到其正确的位置上。然而，在Java实现中，一个细微的错误可能导致算法失效。本文将深入探讨这个问题，并提供正确的实现方式。
问题根源：变量值的改变
以下是一个可能导致循环排序失效的Java代码示例：
立即学习“Java免费学习笔记（深入）”；
static void cyclicSort(int[] arr) {
int i = 0;
while (i < arr.length) {
if (arr[i] != arr[arr[i] - 1]) {
int temp = arr[i];
arr[i] = arr[arr[i] - 1];
arr[arr[i] - 1] = temp;
} else {
i++;
}
}
}这段代码的潜在问题在于表达式 arr[arr[i] - 1]。当执行 arr[i] = arr[arr[i] - 1] 时，arr[i] 的值被改变。这意味着在下一行代码 arr[arr[i] - 1] = temp 中，arr[i] - 1 所代表的索引已经不是原始的预期索引。这会导致元素被放置到错误的位置，从而破坏了排序的正确性。
解决方案：引入辅助变量
为了解决上述问题，可以引入一个辅助变量来存储正确的索引值。修改后的代码如下：
static void cyclicSort(int[] arr) {
int i = 0;
while (i < arr.length) {
int correct = arr[i] - 1;
if (arr[i] != arr[correct]) {
int temp = arr[i];
arr[i] = arr[correct];
arr[correct] = temp;
} else {
i++;
}
}
}在这个版本中，correct 变量存储了 arr[i] - 1 的值。即使 arr[i] 的值在交换过程中发生了改变，correct 的值仍然保持不变，确保了在后续操作中访问的是正确的索引。
完整示例代码：
public class CyclicSort {
static void cyclicSort(int[] arr) {
int i = 0;
while (i < arr.length) {
int correct = arr[i] - 1;
if (arr[i] != arr[correct]) {
int temp = arr[i];
arr[i] = arr[correct];
arr[correct] = temp;
} else {
i++;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
cyclicSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
// 输出: 1 2 3 4 5
}
}注意事项：
- 循环排序适用于包含从 1 到 N 的 N 个不同整数的数组。如果数组包含重复元素或不在这个范围内的元素，则需要进行额外的处理。
- 循环排序是一种原地排序算法，不需要额外的存储空间。
总结：
在实现循环排序算法时，务必注意在交换元素时可能导致索引值发生改变的情况。通过引入辅助变量，可以确保在访问数组元素时使用的是正确的索引，从而避免算法失效。理解并掌握这个细节对于正确使用循环排序至关重要。
