Java实现插入排序经典代码和算法思路

Java技术 潘老师 5个月前 (11-08) 129 ℃ (0) 扫码查看

一、前言

本文主要介绍Java实现插入排序经典代码和具体的算法思路。

插入排序是一种直观且容易理解的排序算法,它的核心思想是将未排序的元素逐个插入到已排序的部分,以构建有序数组。

二、内容

2.1 思路

插入排序的思路非常直观,它模仿我们在现实生活中玩扑克牌的方式。当你拿到一副乱序的扑克牌,你会将每张牌插入到已经有序的手牌中,以确保手牌始终有序。插入排序的核心思想可以概括为以下几个步骤:

  • 从数组的第二个元素开始,将其视为当前未排序区间的唯一元素。
  • 比较当前元素与已排序区间的元素。
  • 如果当前元素小于已排序区间的元素,将当前元素插入到适当的位置,同时将已排序区间的元素向后移动。
  • 重复上述步骤,逐个将未排序区间的元素插入到已排序区间,直到整个数组有序。

2.2 步骤

具体而言,插入排序的步骤如下:

  • 从数组的第二个元素开始,将其暂存为当前元素。
  • 将当前元素与已排序区间的最后一个元素进行比较。
  • 如果当前元素小于已排序区间的元素,将已排序区间的元素向后移动,直到找到当前元素应插入的位置。
  • 将当前元素插入到适当的位置。
  • 继续取下一个未排序区间的元素,重复上述过程,直到整个数组有序。

2.3 代码

使用两个for循环,将未排序的元素逐个插入到已排序的部分,以构建有序数组。下面是插入排序的Java代码实现:

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return; // 如果数组为空或只有一个元素,无需排序
    }
    // 从第二个元素开始,依次插入到已排序区间
    for (int i = 1; i < arr.length; i++) {
        // 通过内层循环进行比较和交换元素,直到找到适当的插入位置
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}
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[] array = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(array);

    System.out.println("排序后的数组:");
    for (int value : array) {
            System.out.print(value + " "); //11 12 22 25 34 64 90
    }
}

在这段代码中,我们使用 `insertionSort()` 方法对给定数组进行插入排序。算法遍历每个元素,并将它插入到已排序序列的正确位置上。在内循环中,我们将比当前元素大的元素向右移动一个位置,以便为当前元素腾出空间并找到其正确位置。最后,我们将当前元素插入到正确的位置上。

插入排序是一种稳定的排序算法,它的时间复杂度为 O(n2n^2n2),其中n是数组的长度。与冒泡排序一样,插入排序也适用于小型数据集,但在某些情况下,它比冒泡排序更加高效。

三、总结

以上就是Java实现插入排序经典代码和算法思路的全部内容。


版权声明:本站文章,如无说明,均为本站原创,转载请注明文章来源。如有侵权,请联系博主删除。
本文链接:https://www.panziye.com/java/10769.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】