chapter_sorting/insertion_sort/ #59
Replies: 22 comments 21 replies
-
发现一个小问题, |
Beta Was this translation helpful? Give feedback.
-
K神,插入排序的核心思想这么写会不会更容易理解和记忆呢:取未排序区间中的某个元素为基准数 |
Beta Was this translation helpful? Give feedback.
-
和斗地主,理扑克一个逻辑哦 |
Beta Was this translation helpful? Give feedback.
-
/**
* 希尔排序
* 是对插入排序的改进,插入排序,如果是5,3,,4,8,1这种最小数在很后面就会进行多次交换
* 希尔排序采用分组加插入排序处理这个问题,将长度/2为分组数量,每个分组在进行插入排序,
* 当步长为1的时候就是简单插入排序,不过此刻数据基本有序,只需要进行少量的交换
* @param ints 数组
* @param gap 组数
*/
public static void shellSort(int[] ints, int gap)
{
// 组数<1结束
if (gap < 1)
{
return;
}
// 有序判断,如果有序就直接结束
// if (isSorted(ints, 0, ints.length))
// {
// return;
// }
// 组数
gap /= 2;
// 步长
int step = gap;
// 对每一组进行排序,i表示每组首元素的下标
for (int i = 0; i < gap; i++)
{
// 对同一组的进行插入排序(和插入排序一样不过插入排序步长为1,这里步长会变)
// j表示同组的下标
for (int j = i + step; j < ints.length; j += step)
{
// 暂存有序区首位元素
int temp = ints[j];
int k = 0;
for (k = j - step; k >= 0; k -= step)
{
if (temp > ints[k])
{
break;
}
// 后移
ints[k + step] = ints[k];
}
// 插入
ints[k + step] = temp;
}
}
// System.out.println("分为" + gap + "组");
// System.out.println(Arrays.toString(ints));
// 递归
shellSort(ints, gap);
} |
Beta Was this translation helpful? Give feedback.
-
为什么我觉得插入排序和冒泡排序基本一样?冒泡排序需要一个tmp临时变量用于交换,插入排序也需要一个base变量。区别在于插入不是每一次都在交换,而是直到找到合适位置,但是我感觉这根本上没多大区别。另外元素“参与”排序的顺序不一样,一个头开始,一个从低开始。本质还是没区别么。。求人解答一下。 |
Beta Was this translation helpful? Give feedback.
-
三点改进:
一简化循环结构,条件放到内部,更易读;
二如果基准元素找到安置位置即跳出循环;
三如果基准元素就是安置位置,无需赋值操作;
public void insertionSort3(int [] array) {
// 外层循环 基准元素依次从左到右
for (int i = 0; i < array.length; i++) {
int base = array[i];
// 内层循环 依次从右到左,遍历已排序区间,查找基准元素合适安置位置
int j = i;
while (j > 0) {
if (array[j - 1] > base) {
// 前边元素依次赋值后续元素,实现移动效果
array[j]= array[j - 1];
} else {
// 如果基准元素已到达指定位置,无序继续比较下去。因为已排序区间为有序,第一个小于基准元素的话,该元素前边都小于基准元素。
break;
}
j --;
}
// 若已排序区间发生元素移动,才会赋值操作。
if (j != i) {
// j的区间为[0,i],不用考虑越界问题。由于break,此处j值对应上轮的array[j-1] 或array[0]。
array[j] = base;
}
}
} |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
😁说到扑克,我都喜欢拿到全部牌后再一张张摸,这样比直接全抓起来理的舒服点。 那么插入排序能不能直接另创一个数组,直接挨个元素往新数组加,加入新数组用二分查找,遇上值相同的直接插入,都不用考虑左右了。 |
Beta Was this translation helpful? Give feedback.
-
k神,感觉可以把希尔排序加上 |
Beta Was this translation helpful? Give feedback.
-
这里 java while语句里面,如果j=0,还会执行 j--么 |
Beta Was this translation helpful? Give feedback.
-
可以填一下 折半插入排序 希尔排序 |
Beta Was this translation helpful? Give feedback.
-
zig标准库的插入排序赋值有点多了,不知在zig标准库中可否改进? |
Beta Was this translation helpful? Give feedback.
-
function insertionSort(nums) {
for (let i = 1; i < nums.length; i++) {
let base = nums[i]
let j = i - 1
while (i >= 0 && nums[j] > base) {
// 交互位置
nums[j + 1] = nums[j]
nums[j] = base
j--
}
}
return nums
} 这样写应该还算插排,唯一差别就是将base和已排好的排比较,大的就交换位置 |
Beta Was this translation helpful? Give feedback.
-
请问大神,nums[j + 1] = base; 这一步不是很理解,他的作用是什么?可以删掉吗? |
Beta Was this translation helpful? Give feedback.
-
有点像打牌的时候抽一张放到手里牌正确位置的感觉 |
Beta Was this translation helpful? Give feedback.
-
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
List<Integer> temp = addItem(list);
for (int i = 1; i < temp.size(); i++) {
for (int j = 0 ; j < i; j++) {
if (temp.get(i) < temp.get(j)) {
Integer tempItem = temp.get(j);
temp.set(j, temp.get(i));
temp.set(i, tempItem);
}
}
}
System.out.println(temp);
}
public static List<Integer> addItem(List<Integer> list) {
list.add(1);
list.add(0);
list.add(16);
list.add(16);
list.add(1);
list.add(3);
list.add(7);
list.add(9);
list.add(11);
list.add(5);
return list;
} 请教下 java这样写 算是插入排序嘛 |
Beta Was this translation helpful? Give feedback.
-
新人刚学算法,下意识用了两个for 循环而不是while,但是这样会多一次赋值操作,不知道怎么优化呢?
|
Beta Was this translation helpful? Give feedback.
-
感觉可以添加一下折半插入排序 |
Beta Was this translation helpful? Give feedback.
-
简单写了一下插入+折半排序,应该没什么问题 /*折半插入排序*/
/*折半插入排序*/
void insertionBinarySort(std::vector<int> &nums) {
int n = nums.size();
// 外循环,已排序区间为 [0, i-1]
for (int i = 1; i < n; i++) {
int base = nums[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] > base) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 将区间 [low, i-1] 的元素右移,腾出位置给 base
for (int j = i; j >= low + 1; j--) {
nums[j] = nums[j - 1];
}
// 将 base 插入到正确位置
nums[low] = base;
}
} |
Beta Was this translation helpful? Give feedback.
-
推荐一个数据结构和算法可视化的网站:VisuAlgo |
Beta Was this translation helpful? Give feedback.
-
看k神的源码之前自己写的,多用了一次循环
|
Beta Was this translation helpful? Give feedback.
-
chapter_sorting/insertion_sort/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_sorting/insertion_sort/
Beta Was this translation helpful? Give feedback.
All reactions