首页 > 文章列表 > 示例:Java代码演示插入排序算法的实现及输出

示例:Java代码演示插入排序算法的实现及输出

java 实现 示例代码 插入排序 运行结果
284 2024-02-18

Java实现插入排序的示例代码和运行结果

插入排序是一种简单且常用的排序算法,在实际应用中有着广泛的应用。本文将介绍如何使用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 -= 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 10, 8, 3};
        System.out.println("排序前:");
        printArray(arr);
        insertionSort(arr);
        System.out.println("排序后:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

代码中的insertionSort方法实现了插入排序算法。它使用一个外层循环遍历未排序部分的每个元素,将元素插入到已排序部分的合适位置。内层循环则是在已排序部分中寻找合适的插入位置,将比当前元素大的元素往后移动。

main方法中,我们定义了一个整型数组arr,初始化了一组无序的元素。首先输出了排序前的数组,然后调用insertionSort方法进行排序,最后输出排序后的数组。

运行结果如下所示:

排序前:
5 2 10 8 3 
排序后:
2 3 5 8 10 

可以看到,经过插入排序算法处理后,原先无序的数组已经成功地按照从小到大的顺序进行了排序。

插入排序的时间复杂度为O(n^2),在处理小规模的数据集时性能较好。然而,对于大规模数据集,插入排序的性能会显著下降,不如其他高效的排序算法。因此,在实际开发中,需要根据具体情况选择适合的排序算法。