首页 > 文章列表 > 用Java编写插入排序的实现及步骤

用Java编写插入排序的实现及步骤

java语言 插入排序算法 步骤与思路
305 2024-02-19

插入排序算法的步骤与思路

插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素插入到已排序序列的合适位置上。

具体步骤如下:

  1. 首先,我们将数组分为两部分:已排序部分和未排序部分。初始时,已排序部分只有一个元素,就是数组的首元素。
  2. 我们从未排序部分中依次取出一个元素,将它与已排序部分中的元素逐个比较,找到合适的位置插入。
  3. 在比较的过程中,我们将已排序部分中的元素向后移动,为插入元素腾出位置。
  4. 最后,我们将未排序部分的元素全部插入到已排序部分的合适位置上,排序完成。

下面是用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 = {5, 2, 8, 1, 9, 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方法,它接受一个整数数组作为参数,并对数组进行插入排序。我们用n表示数组的长度,并使用for循环遍历未排序部分的元素。在每一次遍历中,我们将当前元素arr[i]保存到key变量中,然后向前遍历已排序部分,找到合适的位置插入key。在比较的过程中,我们将较大的元素往后移动一位,为key腾出位置。最后,我们将key插入到正确的位置上,排序完成。

main方法中,我们初始化一个整数数组arr,并调用insertionSort方法对数组进行排序。最后,我们调用printArray方法打印排序后的数组。

通过运行以上代码,可以得到如下的输出结果:

原数组:
5 2 8 1 9 3 
排序后的数组:
1 2 3 5 8 9 

插入排序算法的时间复杂度为O(n^2),其中n是数组的长度。尽管插入排序算法的时间复杂度较高,但它的实现简单,适用于小规模的数组排序。同时,在实际应用中,插入排序算法还具有稳定性的特点。