排序算法----插入和希尔排序
# 排序算法----插入和希尔排序## 1、插入排序
> 插入排序的基本思想：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有 序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排 序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
## 1.1、插入排序代码实现
```java
public static int[] insertSort(int[] initial) {
/**
* 冒泡排序核心代码
*/
//temp临时变量
int temp;
//要插入的位置的下标
int index = 0;
/**
* 代表遍历N-1遍,因为i从1开始，所以长度不需要-1
*/
for (int i = 1; i < initial.length; i++) {
//每次都将要插入的元素，存到临时变量中
temp = initial;
//将要插入的元素，和要插入的元素的前一个数开始比较，直到要插入的元素，大于当前比较的元素
for (index = i - 1; index >= 0 && initial > temp; index--) {
//从有序的数组最后一位开始，一个一个往后移动
initial = initial;
}
/**
*当前元素比要插入的元素小时，代表已经找到了要插入的位置
*因为找到的index所对应的值，是比要插入的元素还要小，所以要插入的元素，要插到当前index的后面，所以要index+1
*/
initial = temp;
}
return initial;
}
```
## 1.2 插入排序存在的问题
**当排在最后的数是较小的数时，后移的次数明显增多，对效率存在很大的影响.，因此，通常把希尔排序称为插入排序的优化版本*
## 2、希尔排序
> 希尔排序的基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含 的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止
## 2.1、希尔排序代码实现
```java
/**
* 希尔排序：通常认为是插入排序的优化版
* 第一次：将元素个数/2，得到分组的个数，将每个分组里面的元素进行比较，如果下标小的元素，值比下标大的元素要大，则两个数进行交换
* 第二次：将上一次的 组数/2，得到新的分组数量，将每组中小的元素放到前面，大的放到后面
* 依次重复上面的操作，直到 上一组/2 = 1，则得到排序后的结果
* 简单来说：就是把数组里面的元素分成个数/2份，然后每一组里面的元素做插入排序，以此类推
* @Param initial 要排序的数组
* @Return 已排序好的数组
*/
public static int[] shellSort(int[] initial){
//temp临时变量
int temp;
//定义每一次的步长，也是分组的个数
int gap;
//插入排序中的位置的下标
int index;
for (gap = initial.length / 2; gap > 0; gap /= 2) {
//中间使用插入排序
for (int i = gap; i < initial.length; i += gap) {
temp = initial;
for (index = i - gap; index >= 0 && initial > temp; index -= gap) {
initial = initial;
}
initial = temp;
}
}
return initial;
}
```
明天更新快速排序、归并排序和基数排序，敬请期待~ if20200606 发表于 2021-3-22 10:54
插入排序好像是冒泡法
冒泡排序是一直对比一直做两个值的交换，插入排序是左边看成有序的，右边一个一个取值，往有序的元素中插入，要插入位置后面的元素，要一个一个往后挪动 xiaokaidada 发表于 2021-3-22 00:02
学习ing，这个和哈希冒泡区别大吗
有区别，时间复杂度和空间复杂度都不太一样，冒泡排序太慢了 可以可以 非常好的帖子 努力学习 很详细，小白需要努力学习 学习ing，这个和哈希冒泡区别大吗
努力学习 已收藏，感谢分享！ 学习思路，感谢 来学习一下，谢谢了
页:
[1]
2