详解Java实现的插入排序算法-java教程-PHP中文网

详解Java实现的插入排序算法

王林

发布： 2024-02-19 12:56:11

原创

565人浏览过

java插入排序算法的实现方法详解

Java插入排序算法的实现方法详解

插入排序是一种简单直观的排序算法，它的原理是将待排序的数列分为已排序和未排序两部分，每次从未排序中取出一个元素，插入到已排序的合适位置。插入排序算法的实现方法相对简单，下面将详细介绍其具体实现方法，并给出相应的代码示例。

秒哒

秒哒-不用代码就能实现任意想法

349

查看详情

算法思路
假设要对一个整数数组arr进行升序排序，初始时将arr[0]视为已排序的部分，其余元素视为未排序的部分。以此为基础，若当前待插入的元素为arr[i]（i从1开始），则从已排序的部分arr[0:i-1]中找到arr[i]应该插入的位置j，将arr[i]插入到位置j，同时将arr[j:i-1]的所有元素依次向后移动一个位置。
代码实现
下面给出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;

            // 将已排序的元素依次向后移动，直到找到arr[i]应该插入的位置
            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 = {5, 2, 8, 3, 1};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

登录后复制