Java直接插入排序法

提示信息

繁华似锦

10月09日发表在 Java 编程语言阅读 111 评论 20 | 免费使用 “AI大模型GPT4.0” 提问

Java直接插入排序法是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排序好的有序序列中，从而得到一个新的、记录增加一的有序序列。

以下是Java实现直接插入排序法的代码：

public class InsertionSort {  
    public static void insertionSort(int[] arr) {  
        int n = arr.length;  
        for (int i = 1; i < n; i++) {  
            int key = arr[i];  
            int j = i - 1;  
            while (j >= 0 && arr[j] > key) {  
                arr[j + 1] = arr[j];  
                j--;  
            }  
            arr[j + 1] = key;  
        }  
    }  
    public static void main(String[] args) {  
        int[] arr = {64, 34, 25, 12, 22, 11, 90};  
        insertionSort(arr);  
        System.out.println("排序后的数组：");  
        for (int num : arr) {  
            System.out.print(num + " ");  
        }  
    }  
}

运行结果：

排序后的数组：  
11 12 22 25 34 64 90

以上代码实现了直接插入排序算法。在该算法中，我们首先从数组的第二个元素开始进行遍历，将这个元素存储为变量key。然后，我们通过逐个比较已排序的子数组中的元素，找到合适的位置将key插入到已排序的子数组中。最后，我们将key插入到它的正确位置，并进行下一轮迭代。这个过程一直持续到整个数组被排序完成。

遇到难题？ "AI大模型GPT4.0、GPT" 是你的私人解答专家！点击按钮去提问......

繁华似锦赞 | 0

最近一次登录：2024-10-25 12:27:41

暂时还没有签名，请关注我或评论我的文章

20条评论

按时间正序按时间倒序按喜欢排序

往如

10月16日

代码清晰简洁，适合入门学习排序算法的基础知识。

赞 0 回复举报

垂暮之年い： @往如

这段评论很切合实际，确实清晰简洁的代码对于学习排序算法至关重要。直接插入排序法虽然简单，但在理解排序算法的基本思想和实现机制上具有很好的示范性。

在实现代码时，以下是一个Java示例，可以更好地帮助理解这个算法的工作原理：

public class InsertionSort {
    public static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;

            // 移动大于 key 的元素
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 2, 9, 1, 5, 6};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}

运行这段代码，你会发现数组从无序到有序的过程其实非常直观，而这种逐步插入和调整的位置变换，也能帮助我们建立对算法的更深了解。

关于排序算法的更多内容，可以参考 GeeksforGeeks - Insertion Sort。这将有助于进一步加深对该算法及其变体的理解。

3天前回复举报

添加新评论

单人床

10月23日

可以加入时间复杂度的分析，比如，在最坏情况下直接插入排序的时间复杂度是O(n^2)，对新手理解性能有帮助。

赞 0 回复举报

有心无感： @单人床

对于直接插入排序的时间复杂度分析无疑是个很好的补充。在学习排序算法时，了解其在不同情况下的性能表现非常重要。

直接插入排序法最坏情况下的时间复杂度是O(n²)，通常发生在输入序列是逆序时。相较之下，最好情况下时间复杂度为O(n)，当输入序列已经有序时，算法只需进行n次比较。

以下是一个简单的Java实现直接插入排序的代码示例，方便新手理解：

public class InsertionSort {
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;

            // 移动大于key的元素
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        insertionSort(array);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

在这个实现中，可以看到，挪动元素的过程在最坏情况下会进行n次外层循环，每次外层循环可能最多进行n次内层循环，因此时间复杂度会达到O(n²)。

如果想进一步了解算法分析，推荐参考这篇关于排序算法的资料：Sorting Algorithms - GeeksforGeeks。希望这些信息对理解插入排序的性能有所帮助。

3天前回复举报

添加新评论

轮回

10月27日

对于小型数组，插入排序是一个很好的选择，因为其内存占用低。更详细的内存分析会提升文章深度。

赞 0 回复举报

利欲： @轮回

对于小型数组而言，插入排序确实是一个不错的选择，因为它的时间复杂度在最佳情况下可以达到O(n)，并且由于其原地排序的特性，内存占用非常小。不过，有趣的是，插入排序在处理近乎有序的数组时性能尤为优越。例如，在数组已经部分排序的情况下，插入排序能够迅速完成排序，显著减少不必要的比较和交换。

下面是一个经典的插入排序的Java实现示例：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // 将arr[j]大于key的元素移到其后
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {12, 11, 13, 5, 6};
        insertionSort(numbers);
        System.out.println("Sorted array: " + Arrays.toString(numbers));
    }
}

为了更加深入地了解插入排序的内存使用情况，可以研究根据数组大小和初始顺序来测量不同情况下的空间复杂度。考虑借助一些在线工具或文献来增强理解，例如 GeeksforGeeks的插入排序分析提供了更详细的分析和示例。这样可以更全面地掌握插入排序在不同应用场景下的优劣。

11月14日回复举报

添加新评论

束缚

11月06日

建议尝试更复杂的用例，比如数组中含有重复元素、负数或是已部分排序的数据，来检验算法的稳定性和效率。

赞 0 回复举报

空自： @束缚

对于直接插入排序法，考虑不同类型的数据确实是个很好的想法。比如在面对重复元素和负数时，这个排序算法的性能会受到影响。以下是一个简单的示例，展示如何在 Java 中实现直接插入排序，同时处理含有重复元素和负数的情况：

public class InsertionSort {
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;

            // 移动比 key 大的元素
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, -1, 3, 2, 5, -3, 0, 2};
        insertionSort(array);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

可以看到，以上代码实现了基本的插入排序，并适用于包含负数和重复元素的数组。通过这种方法测试不同情况，可以帮助我们更好地理解算法的稳定性。

在查阅有关这个算法的细节时，可以参考 GeeksforGeeks的插入排序文章以获取更深入的信息和用例。

11月11日回复举报

添加新评论

小学语文老师

11月10日

文章中的插入排序适合用于了解排序的基本思想。针对算法优化和提升效率，可以进一步探索高级排序算法，如快速排序、归并排序等。

赞 0 回复举报

忘年交： @小学语文老师

对于插入排序的讨论，很容易联想到其作为某些基本排序算法的介绍。虽然插入排序在小规模数据集上表现良好，但在处理大规模数据时，性能往往难以满足需求。考虑到这一点，快速排序和归并排序确实提供了更优雅高效的解决方案。

例如，快速排序的平均时间复杂度为O(n log n)，而归并排序则在最坏情况下也能保持这一效率。实际实现时，代码如下：

快速排序示例

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);
            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

在理解基础排序算法后，逐渐过渡到学习这些高效算法，能够帮助提升解决实际问题的能力。此外，也可以参考一些在线资源，比如 Geeks for Geeks 或 LeetCode 来进一步加深对这些算法的理解与应用。同时，实践是理解算法的关键，通过尝试不同数据集的排序，能够达到更好的学习效果。

11月14日回复举报

添加新评论

野菊花

11月13日

代码示例准确且易于理解，适合初学者实践动手。可以在注释中增加更多的解释，以帮助更好地理解每一步的逻辑。

赞 0 回复举报

你的： @野菊花

对于直接插入排序法的学习，代码的可读性与注释的全面性确实对初学者非常重要。可以考虑在每个关键步骤添加一些注释，例如在数组中插入元素的过程中，解释为何要将已有元素逐一移动。

以下是一个简单的直接插入排序法的实现示例：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i]; // 当前要插入的元素
            int j = i - 1;

            // 移动比 key 大的元素到右边
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // 插入 key
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        insertionSort(array);
        System.out.println(Arrays.toString(array)); // 输出排序后的数组
    }
}

在这个例子中，注释帮助解释了每一部分的逻辑，特别是在元素插入和移动的过程中，如何进行对比和调整位置。若有兴趣，关于算法的理论部分，可以查阅 GeeksforGeeks，这将有助于对插入排序法有更深入的理解。

11月12日回复举报

添加新评论

日光倾城

11月15日

如果对比不同排序算法的效果和效率，加入可视化工具，会让讲解更为生动和直观。

赞 0 回复举报

睡之精灵： @日光倾城

对于插入排序法，确实引入可视化工具可以让理解变得更加生动直观。尤其对于初学者来说，看到数据在排序过程中的变化能够加深对算法本身的理解。

例如，可以使用Java的图形化界面库（如JavaFX或Swing）来动态展示插入排序的过程。以下是一个简单的插入排序实现，可以在每次插入时打印当前数组状态：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
            System.out.println(java.util.Arrays.toString(arr)); // 输出当前数组状态
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        insertionSort(arr);
    }
}

通过这种方式，学生可以清晰地看到每一轮排序后数组的变化，增强对算法步骤的理解。

另外，可以参考在线可视化排序工具，如 Visualgo ，这个工具提供了多种排序算法的可视化展示，对于理解和比较不同算法的效率是非常有帮助的。

3天前回复举报

添加新评论

八神庵

11月18日

在实际开发中，直接插入排序不常用于大型数据集，阅读时希望有对比建议的高级算法参考，比如根据问题规模选择合适的算法策略。可以参考Sorting Algorithms Visualization。

赞 0 回复举报

舞雨火： @八神庵

在选择排序算法时，考虑问题规模确实是非常重要的。直接插入排序在小规模数据集上表现良好，代码实现也相对简单，但随着数据量的增加，其时间复杂度达到O(n²)，开始显得不够高效。

例如，下面是一个简单的直接插入排序的实现：

public void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;

        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

对于较大的数据集，可以考虑使用归并排序或快速排序，时间复杂度均为O(n log n)，在实际应用中效果更佳。比如快速排序的实现示例如下：

public void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(array, low, high);
        quickSort(array, low, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, high);
    }
}

private int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            swap(array, i, j);
        }
    }
    swap(array, i + 1, high);
    return i + 1;
}

private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

对于不同规模的问题，了解各种算法的优势和劣势是非常有益的，可以参考 Sorting Algorithms Visualization 来更好地理解这些基本概念和算法。通过可视化，还能够帮助更直观地理解不同算法在实际中的表现。

4天前回复举报

添加新评论

活着的死人

11月26日

泛型的使用能让这个排序算法更具通用性，不过可能需要额外的类型比较机制，更加贴近Java泛型的使用。

赞 0 回复举报

绯村剑心： @活着的死人

在讨论Java直接插入排序法时，泛型确实提供了一种灵活的方式来处理不同类型的数据。为了让排序算法更智能化，我们可以实现一个比较器接口，以便于自定义排序逻辑。这样，不同的数据类型就可以通过相同的算法进行排序。

以下是一个简单示例，展示如何使用泛型和比较器来实现插入排序：

import java.util.Comparator;

public class GenericInsertionSort {
    public static <T> void insertionSort(T[] array, Comparator<? super T> comparator) {
        for (int i = 1; i < array.length; i++) {
            T key = array[i];
            int j = i - 1;

            while (j >= 0 && comparator.compare(array[j], key) > 0) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        Integer[] numbers = {5, 2, 9, 1, 5, 6};
        insertionSort(numbers, Integer::compareTo);
        for (Integer number : numbers) {
            System.out.print(number + " ");
        }
    }
}

在这个例子中，insertionSort 方法接受一个数组和一个比较器，使其可以对任何类型的数组进行排序，只需提供相应的比较器。此外，通过使用方法引用（如Integer::compareTo）使代码更加简洁。

有关Java泛型和比较器的更多细节，可以参考 Java官方文档。利用这些工具，可以让插入排序法更加灵活和强大，适应不同需求。

前天回复举报

添加新评论

眸中有新痕

12月05日

展示插入排序的实现，便于了解算法的基础理念，建议补充Java的Arrays.sort如何在底层使用插入排序优化，使得知识更具拓展性。

赞 0 回复举报

素颜： @眸中有新痕

对于插入排序算法的实现，确实可以帮助加深对排序算法基础的理解。此外，关于Java中的Arrays.sort()，它在特定情况下（例如对于小规模数组）会使用插入排序作为优化策略，这一点值得关注。

以下是一个简单的插入排序实现示例，便于大家理解其基本原理：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // 将大于key的元素移到右边
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

在实现的过程中，可以注意到插入排序在数据几乎有序的情况下表现优异。而Java的Arrays.sort()在处理小数组（通常是小于或等于一定数量的元素，如 47 个元素）时，采用的是优化过的插入排序。因此，了解这部分的实现对于掌握排序算法的细节与优化手法很有帮助。

此外，想了解更多关于Arrays.sort()的底层实现，可以参考Java官方文档，以获取更深入的信息。

11月14日回复举报

添加新评论

免费图表工具，画流程图、架构图

Java直接插入排序法

快速排序示例

举报评论

删除

删除后，将不可回复，确认要删除？

提示

复制代码，请先登录