1. 插入排序
4 | 2 | 5 | 1 | 6 | 3 |
选定 4, [0,0] 这个区间是已处理的有序区间
现在遍历 [1,5] 这个区间, 逐渐插入已处理的有序区间
把 2 拿出来 与 [4] 比较, 发现 <4 , 把 4 挪到它后面的位置处
_ | 4 | 5 | 1 | 6 | 3 |
---|
考察之前的 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<4
2 号位后移
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
来源: http://www.bubuko.com/infodetail-3123589.html