1 手把手教你排序算法怎么写-德赢Vwin官网 网

手把手教你排序算法怎么写

描述

 

 

排序算法

 

今天以直接插入排序算法,给大家分享一下排序算法的实现思路,主要包含以下部分内容:
 

插入排序介绍

插入排序算法实现

 

手把手教你排序算法怎么写

 

 

排序算法

 

在添加新的记录时,使用顺序查找的方式找到其要插入的位置,然后将新记录插入。


 

以{3,0,9,8,2}无序表按升序排列为例,有序表是一个虚拟的顺序表:
1. 插入排序刚开始,有序表中没有数据,因此直接插入3即可。{3}
 

排序算法

2. 插入0的时候要和有序表中记录3进行比较,0 <3,插入到3的左侧。{0,3}
 

排序算法

3. 插入9的时候,要和有序表中的记录3进行比较,9 > 3 插入到3的右侧{0,3,9}
 

排序算法

4. 插入8的时候,要和有序表中的9进行比较,9 > 8 8>3因此添加到 9和3之间{0,3,8,9}
 

排序算法

5. 插入2的时候,要和有序表中的 9 8 3 0依次比较,确定2位于0和3之间{0,2,3,8,9}
 

排序算法

分析:1、先写框架2、实现排序逻辑3、验证调整代码


 


 

排序算法

2.1 先写框架-我的预期

 

这是一段整理思路的过程。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

int a[] = {3,0,9,8,2};int size = sizeof(a) / sizeof(int);int i;for(i=0;i{ printf("%d ",a[i]);}printf("\n"); // 传递整型数据和长度进去,对数据进行排序insertSort(a,size);
for(i=0;i{ printf("%d ",a[i]);}

预期效果:// 3 0 9 8 2// 0 2 3 8 9

 

 

2.2 函数声明

函数三要素:insertSort函数功能:实现对传入数组的排序形参:数组,数组长度返回值:直接在原有数组中进行排序即可,无需返回值。
先写函数声明

  •  
  •  
  •  
  •  

void insertSort(int a[],int size){ // ......}


2.3 实现排序逻辑1、寻找突破口按照直接插入排序的规则,需要对下标为1以后的每一个数据进行插入排序,先获取到下标为1之后的每一个数据。
 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

void insertSort(int a[],int size){ int i; int j; for(i=1;i { // a[i] 从下标为1开始,每循环一次向后获取到一个数据。
} }

2、寻找排序规律// 使用当前a[i]值和i下标前面的每一个数值进行比较// 如果      a[i-1] > a[i] a[i] = a[i-1] -- a[i]这个数据空间值可能被覆盖掉,//                                                   下面可能还要多次使用到该数据,//                                                    因此可以将这个数据保存下来。// 继续如果 a[i-2] > a[i] a[i-1] = a[i-2]//.....// 如果         a[i-j] < a[i] a[i-j+1] = a[i] --结束本次比较 ,a[i]已经找到它所在的位置了
// 考虑边界// i-j最小值为0,下标不能越界3、伪代码描述先将a[i]的值存起来到变量val里面开始循环比较 j,1<=j<=i(满足i-j最小值为0),每次增加1,保证下标连续比较a[i-j]和val的值
    如果a[i-j] > val,a[i-j]需要向后移动,即a[i-j-1] = a[i-j]    如果a[i-j] <= val;val可以直接放在a[i-j+1]的位置,即a[i-j-1] = val;结束本次循环,进入下一个数的插入排序。
4、代码实现

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

void insertSort(int a[],int size){ int i; int j; for(i=1;i { int val = a[i]; for(j=1;j<=i;j++) { if(a[i-j] <= val) { // 找到val坐在的位置了 a[i-j+1] = val; break; } else { a[i-j+1] = a[i-j]; } 
} } }

5、验证代码

排序算法

出错:没有达到预期,即逻辑存在缺陷


 

6、排查错误

排查错误的时候,可以将比较的次数和每次比较后数组中的结果打印出来,进行排查。

因为数组打印要遍历,为了不影响其他循环变量的值,可以在声明一个变量。
 

排序算法

排序算法

从结果上看,第一次的0没有插入成功,按照逻辑走一遍,发现i=1,j=1,0<3因此3向后移动一步,然后j=2,循环结束了。
也就是意味着,如果当前这个数是数组中的最小的数,应该放在下标为0的这一步操作没有做。
7、修正代码

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

void insertSort(int a[],int size){ int i; int j; for(i=1;i { int val = a[i]; for(j=1;j<=i;j++) { if(a[i-j] <= val) { // 找到val坐在的位置了 a[i-j+1] = val; break; } else { a[i-j+1] = a[i-j];
// 如果当前a[i]是这个数组中最小的元素, // 交换位置后,只剩下0下标的位置了,需要将数据插入到0的位置上。 if(i-j == 0){ a[i-j] = val; } } 

} }


运行代码:

排序算法

本篇内容旨在帮助初学者整理写算法代码思路。
 

 

 

打开APP阅读更多精彩内容
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表德赢Vwin官网 网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉

全部0条评论

快来发表一下你的评论吧 !

×
20
完善资料,
赚取积分