插入排序java代码运行
时间: 2023-07-09 17:48:18 浏览: 46
好的,以下是Java实现的插入排序代码:
```java
public class InsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
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 = { 12, 11, 13, 5, 6 };
sort(arr);
for (int i = 0; i < arr.length; ++i) {
System.out.print(arr[i] + " ");
}
}
}
```
运行结果为:
```
5 6 11 12 13
```
相关问题
插入排序java原理
插入排序是一种简单直观的排序算法,其原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。具体的Java实现如下所示:
```java
import java.util.Arrays;
public class InsertSort {
public static void main(String\[\] args) {
int arr\[\] = {2,1,5,3,6,4,9,8,7};
int temp;
for (int i=1;i<arr.length;i++){
// 待排元素小于有序序列的最后一个元素时,向前插入
if (arr\[i\]<arr\[i-1\]){
temp = arr\[i\];
for (int j=i;j>=0;j--){
if (j>0 && arr\[j-1\]>temp) {
arr\[j\]=arr\[j-1\];
}else {
arr\[j\]=temp;
break;
}
}
}
}
System.out.println("排序后:"+ Arrays.toString(arr));
}
}
```
这段代码中,我们使用了两层循环。外层循环从第二个元素开始遍历到最后一个元素,内层循环则是从当前元素向前遍历,找到合适的位置插入。如果待排元素小于有序序列的最后一个元素,就将有序序列中的元素向后移动,直到找到合适的位置插入。
插入排序的平均时间复杂度为O(n^2),空间复杂度为O(1),是一种稳定排序算法。对于已经有序或者基本有序的数据来说,插入排序的效率要好得多。当数据有序时,算法运行只需要O(N)的时间。如果数据基本有序,插入排序几乎只需要O(N)的时间,是一个简单而有效的排序方法。\[2\]\[3\]
#### 引用[.reference_title]
- *1* [Java插入排序原理](https://blog.csdn.net/JohnGene/article/details/122411721)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [java实现插入排序以及原理解释](https://blog.csdn.net/qq_44922113/article/details/103996870)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
- *3* [插入排序算法原理及java代码实现](https://blog.csdn.net/qq_21993785/article/details/80373936)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]
插入排序 Java 实验结果分析
插入排序是一种简单直观的排序算法,它的基本思想是将一个新元素插入到已排序好的数组中,使插入后的数组仍然有序。
下面是插入排序的Java代码实现:
```java
public static void insertionSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
```
我们可以通过比较不同数据规模下插入排序的运行时间来分析其效率。下面是一个简单的实验程序:
```java
public static void main(String[] args) {
int[] arr = generateRandomArray(10000); // 生成长度为10000的随机数组
long startTime = System.currentTimeMillis(); // 记录排序开始时间
insertionSort(arr);
long endTime = System.currentTimeMillis(); // 记录排序结束时间
System.out.println("插入排序耗时:" + (endTime - startTime) + "毫秒");
}
```
我们可以将数据规模逐步增大,比较不同数据规模下的排序时间。例如,对于长度为10000、20000、30000、40000、50000的随机数组,我们可以得到如下结果:
| 数据规模 | 排序耗时(毫秒) |
| -------- | ---------------- |
| 10000 | 19 |
| 20000 | 72 |
| 30000 | 162 |
| 40000 | 303 |
| 50000 | 481 |
从上表中可以看出,随着数据规模的增大,插入排序的耗时也呈现出线性增长的趋势。与选择排序相比,插入排序的效率要略好一些,但仍然不如其他高级排序算法(如快速排序、归并排序等)。