插入排序,选择排序
插入选择
1.插入排序
4 | 2 | 5 | 1 | 6 | 3 |
选定4, [0,0]这个区间是已处理的有序区间 现在遍历[1,5]这个区间,逐渐插入已处理的有序区间
把2拿出来 与[4]比较,发现<4 ,把4挪到它后面的位置处
考察之前的4所在的位置0位是不是应该插入的地,2与这个预插入位置之前的元素比较,发现已经到头
所以0位是2正确插入的位置 插入后
2 | 4 | 5 | 1 | 6 | 3 |
然后考察5 把5挖出来,看下5是否能放在2这个位置,需要和2位置前面的元素比较 发现5>前面的元素4,所以5 放进2这个位置
2 | 4 | 5 | 1 | 6 | 3 |
继续考察1,把1挖出来,看下1是否能放在3号位置
与之前的2号元素比较,发现1<5,2号元素往后移动
2 | 4 | _ | 5 | 6 | 3 |
2号位置空出来,考察2号之前的元素,发现4>1 ,说明2号位置不是最终插入位置需要把2号之前的元素往后移动
2 | _ | 4 | 5 | 6 | 3 |
1号位置空出来后,考察1号位置是不是最终插入位置,发现1<1号之前的元素2所以1号位置不是最终插入位置继续把1号前一位元素移动到1号
_ | 2 | 4 | 5 | 6 | 3 |
此时考察0号位是不是最终插入位置,发现要比较的位置为-1号 超出范围所以要比较的号位+1位即0号位时最终插入位置
1 | 2 | 4 | 5 | 6 | 3 |
6的插入和之前的5一样
1 | 2 | 4 | 5 | 6 | 3 |
把5号位的3挖出来,看下5号位是不是最终插入位置
3与5号位前一位4号位的6比较,发现小于6,所以需要把4号位的6移动到5号位
1 | 2 | 4 | 5 | _ | 6 |
预插入4号位,拿3与4号位前的3号位比较 发现3<5把3号位往后移动
1 | 2 | 4 | _ | 5 | 6 |
预插入3号位 ,与2号位比较 3<42号位后移
1 | 2 | _ | 4 | 5 | 6 |
预插入2号位,与2号位前位1号位的2比较,发现3>2
终于找到了此次预插入的位即为最终插入位,over
1 | 2 | 3 | 4 | 5 | 6 |
code
insertSort(int arr[],int size){ int i,j; for(i=1;i<size;i++){ int tmp=arr[i]; for (j=i-1;j>=0;j--){ if(arr[j]>tmp){ arr[j+1]=arr[j]; } else{ break; } } arr[j+1]=tmp; }}
选择排序
4 | 2 | 5 | 1 | 6 | 3 |
minindex=0,要考察位0
逐个考察每个元素把相应位置放入相应的元素
第一轮,找到4元素位置应该放的元素,从待考察集合里找到最小的元素的元素与4交换
- 选定第一个待考察的元素 4,把4挖出来,认为这个位置的元素是最小的,minindex=0
- 逐个遍历待考察元素之后的元素,发现2<4,所以 暂时认定2是最小元素,minindex=1
- 继续考察5,发现2<5 ,minindex不变
- 继续考察1 发现 1<2 minindex=3
- 继续考察6 发现 1<6 minindex不变
- 继续考察3 发现 1<3 minindex不变
- 此轮考察完毕,找到minindex=3
4 | 2 | 5 | 1 | 6 | 3 |
交换
1 | 2 | 5 | 4 | 6 | 3 |
第二轮:找到索引为1位置应该存放的元素,从其下一位开始考察
minindex=1,要考察位1
- 考察5,2<5 ,minindex不变
- 考察4 发现2<4 minindex不变
- 考察6 发现2<6 minindex不变
- 考察3 发现 2<3 minindex不变
- 发现minindex与初始的一样,无需交换
1 | 2 | 5 | 4 | 6 | 3 |
依次考察后续位最终数组排序完成
code
void selectSort(int arr[],int size){ int i,j; for(i=0;i<size;i++){ int minIndex=i; for(j=i+1;j<size;j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } if(minIndex!=i){ int tmp=arr[minIndex]; arr[minIndex]=arr[i]; arr[i]=tmp; } }}
code
©著作权归作者所有:来自51CTO博客作者hkui2010的原创作品,如需转载,请注明出处,否则将追究法律责任更多相关文章
- 2021-03-27:给你一个链表的头节点 head ,旋转链表,将链表每个节点向
- 遇到位置不可用怎样解决?
- redis中的 geospatial(地理位置)使用
- 苹果Mac如何修改下载文件预设的路径位置?
- 大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码
- box-sizing和定位原理
- 圣怀布局,网格(容器,项目,单元,轨道,间距,排列,位置,对齐),隐式
- 位置不可用无法访问磁盘结构损坏且无法读取 chkdsk无法修复. 不
- 2021-03-18:给定一个字符串str,只由‘X’和‘.’两种字符构成。‘X