Java实现插入排序程序

在本文中，我们将学习如何在Java中实现插入排序。插入排序是一种基于比较的原地排序算法。这里，维护一个始终排序的子列表。例如，数组的下半部分保持排序。要插入到此已排序子列表中的元素必须找到其适当的位置，然后插入到该位置。因此得名插入排序。

顺序搜索数组，并将未排序的项目移动并插入到已排序的子列表（在同一个数组中）。

问题陈述

对于给定的数组，编写一个Java程序来实现插入排序。

输入

array[] = {10, 20, 25, 63, 96, 57}

输出

10 20 25 57 63 96

插入排序算法

实现插入排序算法的步骤：

  • 如果它是第一个元素，则已排序。返回1；
  • 选择下一个元素
  • 与已排序子列表中的所有元素进行比较
  • 将已排序子列表中所有大于要排序的值的元素右移
  • 插入for循环中的值
  • 重复此过程，直到列表排序

伪代码

以下是插入排序算法的伪代码：

Algorithm: Insertion-Sort(A)
for j = 2 to A.length
   key = A[j]
   i = j – 1
   while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i -1
   A[i + 1] = key

Java实现插入排序程序

以下是实现插入排序的Java程序：

public class InsertionSort {
   public static void main(String args[]){
      int array[] = {10, 20, 25, 63, 96, 57};
      int size = array.length;

      for (int i=1 ;i< size; i++){
         int val = array[i];
         int pos = i;

         while(array[pos-1]>val && pos>0){
            array[pos] = array[pos-1];
            pos = pos-1;
         }
         array[pos] = val;
      }

      for (int i=0 ;i< size; i++){
         System.out.print(" "+array[i]);
      }
   }
}

输出

10 20 25 57 63 96

时间复杂度： O(N^2)
辅助空间： O(1)

代码解释

上面的Java程序实现了插入排序算法。它首先初始化一个整数数组，然后确定数组的长度。主要的排序逻辑发生在一个for循环中，该循环从第二个元素开始迭代数组。对于每个元素，将当前值 val 与数组已排序部分的元素进行比较。如果已排序部分中的任何元素大于val，则循环将这些元素向右移动，为插入腾出空间。

最后，将val放在其正确的位置，确保数组的左侧保持排序。排序后，程序按顺序打印已排序的数组元素。

更新于：2024年9月11日

1K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告