数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
代码解释
上面的Java程序实现了插入排序算法。它首先初始化一个整数数组，然后确定数组的长度。主要的排序逻辑发生在一个for循环中，该循环从第二个元素开始迭代数组。对于每个元素，将当前值 val 与数组已排序部分的元素进行比较。如果已排序部分中的任何元素大于val，则循环将这些元素向右移动，为插入腾出空间。
最后，将val放在其正确的位置，确保数组的左侧保持排序。排序后，程序按顺序打印已排序的数组元素。
更新于：2024年9月11日
1K+ 次浏览
广告