详解Java常用排序算法-插入排序_插入排序java资源-CSDN文库

需积分: 1 34 浏览量 2023-08-26 15:56:17 上传评论收藏 14KB DOCX 举报

资源推荐

资源详情

资源评论

插入排序（Insertion Sort）

插入排序是一种简单的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，

从而得到一个新的、记录数增 1 的有序表。

import org.junit.jupiter.api.Assertions;

import java.util.Arrays;

public class Insertion {

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;

// 将当前值 key 和前面的值进行比较，如果前面的值>key 则将值往后移 1 位

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j--;

}

// 在不小当前值 key 的位置，插入当前值 key

arr[j + 1] = key;

}

}

public static void main(String[] args) {

int[] arr = {5, 2, 8, 3, 1, 6};

int[] expectedArr = {1, 2, 3, 5, 6, 8};

Insertion.insertionSort(arr);

System.out.println("arr = " + Arrays.toString(arr));

Assertions.assertArrayEquals(expectedArr, arr);

}

}

在上面的代码中， insertionSort 函数接受一个整数数组作为输入，并使用插入排序算法对

其进行排序。外部循环从第二个元素开始，因为我们将第一个元素视为已排序部分。在内部

循环中，我们将要插入的元素与已排序部分的元素进行比较，如果要插入的元素小于已排序

部分的元素，则将已排序部分的元素向右移动一位，以便为要插入的元素腾出空间。在内部

循环结束后，我们将要插入的元素插入到正确的位置。在每次外部循环迭代后，我们可以确

保前 i 个元素已经被排序。

插入排序的时间复杂度为 O(n^2)，这使得它在大型列表和实际应用中效率低下。但是，插入

排序的实现非常简单，它在小型列表上的性能非常好。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

内容反馈

烈日下的奔跑

粉丝: 1066
资源: 230

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip