Java 插入排序
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。以下是插入排序的Java实现:
public class InsertionSort {
// 插入排序算法实现
public static void insertionSort(int[] array) {
int n = array.length;
for (int i = 1; i < n; ++i) {
int key = array[i];
int j = i - 1;
// 将array[i]插入到已排序部分array[0..i-1]
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
// 打印数组
public static void printArray(int[] array) {
int n = array.length;
for (int i = 0; i < n; ++i) {
System.out.print(array[i] + " ");
}
System.out.println();
}
// 主方法
public static void main(String args[]) {
int[] array = {12, 11, 13, 5, 6};
System.out.println("排序前的数组:");
printArray(array);
insertionSort(array);
System.out.println("排序后的数组:");
printArray(array);
}
}
代码解释
- 插入排序方法
insertionSort(int[] array)
:n
表示数组的长度。- 外层循环
for (int i = 1; i < n; ++i)
遍历数组中的每一个元素,从第二个元素开始(假设第一个元素是已排序的)。 key
保存当前要插入的元素array[i]
。- 内层循环
while (j >= 0 && array[j] > key)
从已排序部分的最后一个元素开始向前扫描,找到key
应该插入的位置。 - 如果已排序部分的元素大于
key
,则将其向后移动一个位置。 - 最后,将
key
插入到正确的位置array[j + 1]
。
- 打印数组方法
printArray(int[] array)
:- 遍历数组并打印每一个元素。
- 主方法
main(String args[])
:- 创建一个示例数组。
- 打印排序前的数组。
- 调用
insertionSort
方法对数组进行排序。 - 打印排序后的数组。
复杂度分析
- 时间复杂度:
- 平均和最坏情况:O(n^2),其中
n
是数组的长度。 - 最好情况:O(n),当数组已经是有序的时候。
- 平均和最坏情况:O(n^2),其中
- 空间复杂度: O(1),因为排序是原地进行的,不需要额外的存储空间。
插入排序对于小规模数据或部分有序的数据表现良好,但在处理大规模数据时效率较低。
原文地址:https://blog.csdn.net/FlyingJiang/article/details/142769071
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!