Java数据结构与算法之插入排序

59 阅读 0 评论 39 点赞

我是靠谱客的博主无心白云，最近开发中收集的这篇文章主要介绍Java数据结构与算法之插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路分析

插入排序，从数组0号索引开始，依次让0 ~ 0、0 ~ 1、0~2 … 直到0 ~ i有序。因为0 ~ 0是有序的，所以遍历从数组索引为1的元素开始，将新遍历的元素与排好的元素最后一个开始比较大小，大的放末尾，小的继续与前面的元素比较，直到所有元素排序完毕

代码实现

package DataStructures;

// 插入排序
public class Insertion {

    public static int[] insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        // 从0开始, 依次让0~i有序（因为0到0已经有序，所以i从1开始）
        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);
            }
        }
        return arr;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

测试代码

package DataStructuresTest;

import DataStructures.Insertion;

public class InsertionTest {

    public static void main(String[] args) {
        int[] arr = {3, 7, 9, 2, 4, 1};
        int[] result = Insertion.insertionSort(arr);
        for (int i : result) {
            System.out.println(i);
        }
    }
}