当前位置：首页 > article >正文

Java算法之梳排序（Comb Sort）

article 2024/11/15 10:07:40

梳排序简介

梳排序（Comb Sort）是冒泡排序的一个变种，其核心思想是在比较相邻元素之前先进行更大步长的比较。这种算法的名称来源于其工作方式类似于梳头发时的动作，先大范围地移动，然后逐渐减小移动的步长，直至相邻。

算法原理

梳排序的工作原理包括以下几个步骤：

初始化步长：设置一个初始步长，通常为数组长度的缩放因子，如gap = n/1.3。
比较与交换：从数组的开头开始，比较相隔gap个元素的两个数，如果前一个数大于后一个数，则交换它们。
缩减步长：将步长减少，通常每次减半，直到步长为1。
完成排序：当步长缩减到1时，算法退化为冒泡排序，完成剩余的排序工作。

代码实现

以下是使用Java实现梳排序的示例代码：

public class CombSort {
    // 辅助函数，用于交换数组中的两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 梳排序主函数
    public static void combSort(int[] arr) {
        int n = arr.length;
        int gap = n - 1; // 初始化步长为数组长度减1
        boolean swapped;

        do {
            gap = (int)(gap / 1.247); // 缩减步长，1.247是接近黄金分割比的值
            swapped = false;

            for (int i = 0; i < n - gap; i++) {
                if (arr[i] > arr[i + gap]) {
                    swap(arr, i, i + gap);
                    swapped = true;
                }
            }
        } while (gap > 1 || swapped); // 当步长大于1或者发生了交换时继续
    }

    public static void main(String[] args) {
        int[] arr = {8, 4, 3, 7, 6, 5, 2, 1};
        combSort(arr);
        System.out.println("排序后的数组: ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}