排序算法-------插入排序（直接插入排序和希尔排序）
目录
排序算法-------插入排序（直接插入排序和希尔排序）
1、直接插入排序
2、希尔排序
1、直接插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
1.1 算法思路
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
1.2 算法动态图解
1.3 算法分析
| 算法 | 最好时间 | 最坏时间 | 平均时间 | 额外空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序算法 | O(n） | O(n2) | O(n2) | 1 | 稳定 |
1.4 算法实现
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** * 直接插入排序算法 */ public class InsertSort { public void sort(int[] nums){ if(nums == null || nums.length == 0){ return; } int cur; for(int i = 0; i < nums.length -1; ++i){ cur = nums[i +1]; //标记当前插入的数字 int preIndex = i; //标记可以插入的下标范围 while(nums[preIndex] > cur){ nums[preIndex + 1] = nums[preIndex]; preIndex--; } nums[preIndex + 1] = cur; } } public static void main(String args[]){ int[] nums = new int[]{5,69,54,21,5,36,7,84}; InsertSort insertSort = new InsertSort(); insertSort.sort(nums); for(int num : nums){ System.out.print(num + " "); } } }
运行结果：
5 5 7 21 36 54 69 84
2、希尔排序
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2.1 算法思路
设置一个增量，然后按照这个增量对元素进行分组，设数组长度为length，那么增量就设置为length/2,length/4.....1。然后对每个分组进行插入排序，直到增量为1，那么排序结束。例如：
2.2 算法分析
| 算法 | 平均时间 | 最优时间 | 最坏时间 | 额外空间 | 稳定性 |
| 希尔排序 | O(nlogn) | O(nlogn) | O(nlogn) | 1 | 不稳定 |
2.3 算法实现
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/** * 希尔排序实现 */ public class XierSort { public static void sort(int[] nums){ if(nums == null || nums.length == 0) return; int len = nums.length / 2; int cur; while (len > 0){ for(int i = len; i < nums.length; ++i){ cur = nums[i]; int temp = i - len; while (temp >= 0 && nums[temp] > cur){ nums[temp + len] = nums[temp]; temp -= len; } nums[temp + len] = cur; } len /= 2; } } public static void main(String args[]){ int[] nums = new int[]{5,69,54,21,5,36,7,84}; XierSort.sort(nums); for(int num : nums){ System.out.print(num + " "); } } }
运行结果：
5 5 7 21 36 54 69 84
参考：
https://www.cnblogs.com/guoyaohua/p/8600214.html
最后
以上就是糟糕书本最近收集整理的关于排序算法-------插入排序（直接插入排序和希尔排序）排序算法-------插入排序（直接插入排序和希尔排序）的全部内容，更多相关排序算法-------插入排序（直接插入排序和希尔排序）排序算法-------插入排序（直接插入排序和希尔排序）内容请搜索靠谱客的其他文章。
发表评论 取消回复