Java算法之循环排序（Cyclic Sort)
简介
循环排序（Cyclic Sort）是一种最小化移动次数的原地排序算法，它利用了数组元素的初始顺序。如果一个元素不在它最终应该在的位置，循环排序会找到这个元素应该在的位置，并将该位置的元素交换过来，直到这个循环结束。这个过程会将整个循环中的所有元素放到正确的位置上。
算法步骤
- 遍历数组，对于每个元素，如果它不在正确的位置上，找到它应该在的位置。
- 交换当前元素和它应该在的位置的元素。
- 重复步骤2，直到没有元素需要交换，形成一个循环。
//cyclicSort 方法接受一个整型数组 arr 作为参数，执行循环排序。
//通过 correctIndex 计算每个元素应该在的位置，并进行交换。
//使用 swap 方法来交换数组中的两个元素。
//main 方法中，我们初始化一个数组，然后调用 cyclicSort 方法进行排序，并打印排序后的结果
public class CyclicSort {// 循环排序方法public static void cyclicSort(int[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {// 找到应该在位置i的元素int correctIndex = arr[i] - 1;// 如果当前元素已经在正确的位置上，则继续下一个元素if (arr[i] == arr[correctIndex]) {continue;}// 交换当前元素到它应该在的位置swap(arr, i, correctIndex);// 如果交换后的元素和当前索引指向同一个位置，跳出循环while (arr[i] == arr[correctIndex]) {i++;}}}// 辅助方法，用于交换数组中的两个元素private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {3, 5, 4, 6, 2, 1};cyclicSort(arr);// 打印排序后的数组for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}优点
- 原地排序：循环排序不需要额外的存储空间，空间复杂度为O(1)。
- 稳定性：循环排序是稳定的排序算法，相等的元素不会交换位置。
- 效率：对于部分已排序或具有特定模式的数组，循环排序可以非常高效。
缺点
- 最坏情况效率低：如果数组完全逆序，循环排序的时间复杂度为O(n^2)。
- 适用性限制：循环排序只适用于数组中的每个元素都是唯一的情况。
时间复杂度和空间复杂度分析
- 时间复杂度：平均情况下为O(n)，最坏情况下为O(n^2)。
- 空间复杂度：O(1)，不需要额外的存储空间。
使用场景
- 当数组元素具有唯一性，并且希望最小化移动次数时。
- 在内存受限的环境中，需要原地排序时。