插入排序_堆排序的详细过程

插入排序_堆排序的详细过程一 思想 插入排序的基本思想就是把数组看成两部分,前面一部分是有序排好的数组,后面一部分是待排的数组 比如 3,1,2,5 四个数,一开始可以把3看做前面一部分,1,2, 5为后面待排的无序数组 代码分步分析 1 package Sort; 2 3 import java.util.Arrays;

插入排序_堆排序的详细过程"

一—思想

插入排序的基本思想就是把数组看成两部分,前面一部分是有序排好的数组,后面一部分是待排的数组

比如 3,1,2,5 四个数,一开始可以把3看做前面一部分,1,2, 5为后面待排的无序数组

代码分步分析

 1 package Sort;
 2 
 3 import java.util.Arrays;
 4 
 5 public class insertSort {
 6     public static void main(String[] args) {
 7         int[] arr = {3, 1, 2, 5};
 8         insertSort(arr);
 9     }
10 
11     public static void insertSort(int[] arr) {
12         // 使用逐步推导的方式来讲解,便于理解
13         // 第一轮{3, 1, 2, 5}->{1, 3, 2,5}
14        
15             // 定义待插入的数
16             int insertVal = arr[1];
17             int insertIndex = 1 - 1; // 即arr[1]的前面这个数的下标
18 
19             // 给insertVal找到插入的位置
20             // 说明
21             // 1.insertIndex >= 0 保证在给insertVal 找插入位置的时候不越界
22             // 2.insertVal < arr[insertIndex]说明待插入的数还没有找到适当位置
23             // 3.就需要将arr[insertIndex]后移
24 
25             while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
26                 arr[insertIndex + 1] = arr[insertIndex];
27                 insertIndex--; // 让待插入的数和前面的数去比较
28             }
29             // 当退出while循环,说明插入位置找到,insertIndex + 1;
30             arr[insertIndex + 1] = insertVal;
31             System.out.println("第1轮插入后");
32             System.out.println(Arrays.toString(arr));
33    
34 
35        // 第2轮
36         insertVal = arr[2];
37         insertIndex = 2 - 1;
38         while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
39             arr[insertIndex + 1] = arr[insertIndex];
40             insertIndex--; // 让待插入的数和前面的数去比较
41         }
42         arr[insertIndex + 1] = insertVal;
43         System.out.println("第2轮插入后");
44         System.out.println(Arrays.toString(arr));
45 
46         // 第3轮
47         insertVal = arr[3];
48         insertIndex = 3 - 1;
49         while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
50             arr[insertIndex + 1] = arr[insertIndex];
51             insertIndex--; // 让待插入的数和前面的数去比较
52         }
53         arr[insertIndex + 1] = insertVal;
54         System.out.println("第3轮插入后");
55         System.out.println(Arrays.toString(arr));
56 
57     }
58 
59 }

观察一下上面的代码,可以发现1-3步中有大量重复的代码,所以我们可以把1-3用for循环来改进

改进代码

 1 for (int i = 1; i < arr.length; i++) {
 2             // 定义待插入的数
 3             int insertVal = arr[i];
 4             int insertIndex = i - 1; // 即arr[i]的前面这个数的下标
 5 
 6             // 给insertVal找到插入的位置
 7             // 说明
 8             // 1.insertIndex >= 0 保证在给insertVal 找插入位置的时候不越界
 9             // 2.insertVal < arr[insertIndex]说明待插入的数还没有找到适当位置
10             // 3.就需要将arr[insertIndex]后移
11 
12             while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
13                 arr[insertIndex + 1] = arr[insertIndex];
14                 insertIndex--; // 让待插入的数和前面的数去比较
15             }
16             // 当退出while循环,说明插入位置找到,insertIndex + 1;
17             arr[insertIndex + 1] = insertVal;
18             System.out.println("第" + i + "轮插入后");
19             System.out.println(Arrays.toString(arr));
20         }

改变的部分就只有红字部分,其余不变。

 

 

package Sort;

import java.util.Arrays;

public class insertSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1};
insertSort(arr);
}

public static void insertSort(int[] arr) {
// 使用逐步推的方式来讲解,便于理解
// 第一{101, 34, 119, 1}->{34, 101, 119,1}
for (int i = 1; i < arr.length; i++) {
// 入的
int insertVal = arr[i];
int insertIndex = i - 1; // arr[1]的前面这个数的下

// insertVal入的位置
//
// 1.insertIndex >= 0 insertVal 找插入位置的候不越界
// 2.insertVal < arr[insertIndex]明待入的数还没到适位置
// 3.就需要arr[insertIndex]后移

while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--; // 入的和前面的去比
}
// 退出while入位置到,insertIndex + 1;
arr[insertIndex + 1] = insertVal;
System.out.println("" + i + "轮插入后");
System.out.println(Arrays.toString(arr));
}

/*// 2
insertVal = arr[2];
insertIndex = 2 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--; // 入的和前面的去比
}
arr[insertIndex + 1] = insertVal;
System.out.println("2轮插入后");
System.out.println(Arrays.toString(arr));

// 第三
insertVal = arr[3];
insertIndex = 3 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--; // 入的和前面的去比
}
arr[insertIndex + 1] = insertVal;
System.out.println("2轮插入后");
System.out.println(Arrays.toString(arr));
*/
}

}

今天的文章插入排序_堆排序的详细过程分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/53372.html

(0)
编程小号编程小号
上一篇 2023-08-30 15:17
下一篇 2023-08-30 15:46

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注