文章目录简介算法讲解插入排序选择排序简介排序算法是算法中经典的例子而且也是重要的算法因此掌握排序算法是很重要的。常用的算法有七种而这七种算法又可以分成四个大类如下所示接下来我将对插入排序跟希尔排序进行讲解以及代码实现。算法讲解插入排序直接插入排序直接插入排序的思想是假设现在有一个数组现有一个下标end从0到end这个区间是有序的此时我们要将下标为end1的值也就是这一段区间的后面一个值插入到这已经有序的区间当中使得加入了这个值的新区间变得有序这就是插入的逻辑。而我们要想使得整个数组变得有序就需要将end从0开始设置然后不断地让下标为end1的值往前面的区间进行插入直到这个end一直等于数组的倒数第二个数的下标也就是size-1-1,这里size为数组大小数组的倒数第二个数的下标就为size-2当end为size-2时此时【0end】的值都是有序的就差数组的最后一个数还未往前插入这一步做完以后整个数组变成有序数组。voidInsertSort(int*arr,intsize){for(intend0;endsize-1;end)//这里end不能等于size-1也就是上面说的end不能等于数组的最后一位因为这里的逻辑是end跟end1的值相比较如果end为最后一个数的下标那么end1就越界了{for(end;end0;end--)//确定end之后插入的具体做法是比较两者大小符合要求就进行交换然后继续做判断如果不符合要求那么就直接退出因为【0end】都是有序的只要不符合那么更前面的数更不符合了{if(arr[end]arr[end1]){Swap(arr[end],arr[end1]);}elsebreak;}}}希尔排序希尔排序跟插入排序的思路是极其一模一样的但是希尔排序是直接插入排序的优化版本在希尔排序中在进行数据之间的比较时我们依然是要先确定end的值但是比较时我们不再是end跟end1比较而是end跟endgap比较这里的gap是一个变量当gap1时就是上面的直接插入排序直接插入排序有一个弊端就是当整个数组数据非常混乱或者完全就是一个倒序数组时它要经过很多次的交换而每一次交换都是一次开销当这个次数越多排序的效率就越低因此我们使用直接插入排序就很吃瘪而希尔排序比直接插入排序多做的一件事就是它是先让整个数组变得“局部有序”希尔排序使用了gap变量通过调整gap的值进行排序至于怎么排序怎么变得局部有序又是怎么变成完全有序往下看。这里是我在网上找的一张希尔排序的图片这张图片看起来复杂但是理解了其中逻辑就很简单先看当gap1的情况这种情况下就跟直接插入排序是一模一样的gap2时我们可以发现整个数组的比较逻辑是一个数跟2个位置前的数依次进行比较把直接插入排序的思路用到这里来看我们随机找一个end比如end6也就是指向数字8的下标时我们要找到跟它比较的值在直接插入排序中是end1而在这里是endgap也就是end2即指向数字5的下标然后就是跟直接插入排序一样的逻辑进行插入这样就能做到局部有序等到gap1也就是跟直接插入排序一样时就能减少交换的次数提高效率。通过看图片我们发现end的最大取值其实要满足endsize-gap因为end下标的值是要跟endgap对应的值去进行比较的而endgap值是不能大于或者等于size的所以必须满足endsize-gap至于gap的值如何变化看下面代码实现voidShellsort(int*arr,intsize){intgapsize;while(gap1){gapgap/31;//这里的1操作是保证最后的gap一定等于1而这个式子取得的gap能够保证效率最高感兴趣的小伙伴自己去查阅一下相关资料for(intend0;endsize-gap;end){for(intiend;i0;i-gap){if(arr[i]arr[igap]){Swap(arr[i],arr[igap]);}elsebreak;}}}}选择排序直接选择排序选择排序顾名思义就是要选择直接选择排序的思想也不难理解假设目前有一个数组下标范围【beginend】要使得这个数组的【0begin-1】跟【end1size-1】区间是有序的【beginend】区间是未排序的当beginend时就说明整个数组排序完毕那么我们就要从【beginend】区间内选出最小的数以及最大的数往begin跟end位置放然后再调整begin跟end的位置这样就能够实现排序如果想不明白可以在纸上画一画肯定能懂的下面给出具体代码voidChoicesort(int*arr,intsize){intbegin0,endsize-1;intmax,min,cur;while(beginend){maxmincurbegin;while(curend){if(arr[cur]arr[max])maxcur;if(arr[cur]arr[min])mincur;cur;}Swap(arr[min],arr[begin]);if(maxbegin)maxmin;Swap(arr[max],arr[end]);begin;end--;}}这里有一个需要特别注意的一步是 if (max begin) max min 这一步必须要做因为如果在maxbegin的情况下把min位置的值跟begin位置的值交换以后会导致max对应的值反而变成最小的值了这个时候就需要更新max的位置也就是原来的min位置这里可以画图理解一下。堆排序要想了解堆排序首先得要先了解堆这个数据结构的特性具体的可以参考我博客中的有关堆的介绍。堆排序的思路不难理解就是要先把堆建立好然后选择堆顶元素跟堆最后的元素进行交换将堆的size减一之后继续在堆顶的位置向下建堆每一次建堆后堆顶元素就是剩余元素的最大/小值把这个值放到剩余元素的最后就是将最大/小的值选出来排好如此循环当堆的size只剩下一个的时候整个数组也就完成了排序。voidadjustdown(int*arr,intparent,intsize){intchildparent*21;while(childsize){intleftchildchild,rightchildchild1;if(rightchildsizearr[leftchild]arr[rightchild])child;if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);parentchild;childparent*21;}elsebreak;}}voidHeapsort(int*arr,intsize){intchildsize-1;intparent(child-1)/2;while(parent0){adjustdown(arr,parent,size);parent--;}//到这里堆建立完毕while(size0){Swap(arr[0],arr[size-1]);size--;adjustdown(arr,0,size);}}在二叉树中child节点的表达式为2*parent1这个式子求出来是左孩子而parent节点则是child-1/2。到这里已经把插入排序跟选择排序讲完剩下的排序请看常见七种算法的代码实现以及细节理解2喜欢的小伙伴记得点点关注点点赞哦感谢支持