一、什么是插入排序
直接插入排序(Straight Insertion Sort)的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程
二、插入排序图详解
用图表示加深对快速排序的理解
1 一个数组里面有 30 40 60 10 20 50
第i个无序数排列,去0到i-1位置里面找比i的值大的位置j,然后坐在从j位置i-1位置往后移动
三、代码实现
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77package com.example.weixindemo.suanfa; public class InsertionSort { /** * 插入排序(升序) * @param a 待排序数组 */ public static void insertionSortAes(int[] a){ int i;//在排序第i个数 int j;//第i个数插入在第j个数后面 int k;//从第k个原数开始移动位置 for(i=1;i<a.length;i++){ //查找第i个原数插入的位置 for(j=i-1;j>=0;j--){ if (a[j]<a[i]){ break; } } //开始移动数据 if(j!=i-1){ int temp = a[i]; for(k=i-1;k>j;k--){ a[k+1] = a[k]; } a[k+1] = temp; } } } /** * 插入排序(降序) * @param a 待排序数组 */ public static void insertionSortDes(int[] a){ int i;//在排序第i个数 int j;//第i个数插入在第j个数后面 int k;//从第k个原数开始移动位置 for(i=1;i<a.length;i++){ for(j=i-1;j>=0;j--){ if(a[j]>a[i]){ break; } } if(j!=i-1){ int temp=a[i]; for (k=i-1;k>j;k--){ a[k+1] = a[k]; } a[k+1] = temp; } } } public static void main(String[] args) { int i; int a[] = {30,40,60,10,20,50}; System.out.printf("before sort:"); for (i=0; i<a.length; i++) System.out.printf("%d ", a[i]); System.out.printf("n"); insertionSortAes(a); System.out.printf("after sort:"); for (i=0; i<a.length; i++) System.out.printf("%d ", a[i]); System.out.printf("n"); insertionSortDes(a); System.out.printf("after sort:"); for (i=0; i<a.length; i++) System.out.printf("%d ", a[i]); System.out.printf("n"); } }
四、结果输出
最后
以上就是追寻冬天最近收集整理的关于数据结构与算法 (三)插入排序的全部内容,更多相关数据结构与算法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复