Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
0.常见的排序算法:
常见的排序算法有这些.将会分成几个章节讲完,感兴趣的uu们可以关注下我的排序专栏,方便和后期观看.
这章重点讲交换排序中的:冒泡排序与快速排序.其中冒泡排序比较简单,而快速排序就有点困难了.话不多说我们开始
1.冒泡排序:
冒泡排序十分的简单,也是大多数朋友刚学习编程时就学会的排序方法.顾名思义:要排序的数就像一个气泡一样,一直往上冒,直到到达水面(也就是目标位置),每冒一次,下一次的气泡需要走的路程就-1,也就是水面下降.
其时间复杂度为O(N^2)
1.1冒泡排序代码实现:
void BubbleSort(int *a,int len) { for(int i=0;i<len;i++) for(int j=1;j<len-i;j++) { if(a[j]>a[j-1]) { swap(a[j],a[j-1]); } } }
冒泡排序就写好啦,但这里可以优化一下:当剩下的数组有序的时候,还需要冒完全程嘛?
所以当有一次遍历发现一次都没有交换的时候,此时就可以推出冒泡.因为数组已经有序
1.2冒泡排序代码优化:
void BubbleSort(int *a,int len) { for(int i=0;i<len;i++) { int exchage=1; for(int j=1;j<len-i;j++) { if(a[j]>a[j-1]) { swap(a[j],a[j-1]); exchage=0; } } if(exchage)break; } }
2.快速排序:
一听这个名字有没有觉得很高大,快速排序.
我们通过一个动图来了解一下他是怎样工作
由浅入深,我们先来了解一下他单趟排序的过程.
首先先确定一个Key,这个时候一般是取第一个数字为key.
之后设定两个哨兵位,分别为左边第一个位置与右边第一个位置.
因为取定key的位置为.左边第一个.
所以要从右边先开始走.当右边遇到比key小的数字的时候就停下来.
这时候左边开始走,当遇到比key大的数字的时候.就停下来.
交换此时左边与右边所代表的数字
右边重新开始.重复这个过程.
直到两边相遇.将key和其交换即可.
(为什么相遇了交换则完成单趟排序以及解释下为什么要从key的对面开始走)
相遇了就说明,左边的都是比key小的.右边的都比key要大,则所以把key与当前这个位置交换就可以了
进而就可以解释为什么,要先从key的对面走.
因为要找比key小的,这样相遇的时候右边停留的才是比key小的(因为右边遇到小的先停下来)
之后再将其分为左半边与右半边进行上面的过程即可.
2.1Hore法:
刚刚介绍的这种方法就是Hore排序的方法,后面大部分的方法都是基于其基础上进行改进,所以我们先来看看他的代码实现
void PartSort1(int* a, int left, int right)//hore { if(left>=right)return ; int key =left; int i=left,j=right; while(i<j) { while(i<j&&a[j]>=a[key])j--; while(i<j&&a[i]<=a[key])i++; if(i<j)swap(a[i],a[j]); } swap(a[key],a[i]); PartSort1(a,left,i-1); PartSort1(a,j+1,right); }
注意,当中哨兵位寻找停下位置的时候,一定要加上等于的判断 ,否则当有一个数据等于key的值时,哨兵就会在这卡住.
2.2挖坑法:
其内容大致也与Hore法相似,不过是换了一种形式来进行排序.
先将Key作为坑挖出
之后右哨兵指向的位置(比key小的值)填入坑位中,转换坑位.
之后左哨兵指向的位置(比key大的值)填入坑位中,继续交互坑位
最后相遇的位置即为Key存入的位置
总的来说与Hore法大同小异.
不过与Hore法不同的是,必须先将Key的值保存下来(因为过程中产生了交换),否则最后填入的是交换后的值
2.2.1挖坑法代码实现:
void PartSort3(int* a, int left, int right)//挖坑 { if(left>=right)return ; key=left; int begin=left,end=right; int value=a[begin]; int hole=begin; while(begin<end) { while(begin<end&&a[end]>=value)end--; a[hole]=a[end]; hole=end; while(begin<end&&a[begin]<=value)begin++; a[hole]=a[begin]; hole=begin; } a[hole]=value; PartSort3(a,left,hole-1); PartSort3(a,hole+1,right); }
2.3双指针法:
这个方法就与上面的有本质的区别了.先来看看动图理解下
其本质就是利用一段区间来维护比key大的数字.(用这个思想我们来理解下)
首先依旧先确定Key的值,因为prev与cur这段区间内维护的是比其大的值.
当cur指向的元素比key大的时候,直接后移cur,表示收入这段区间内
当cur指向元素比key小的时候,前移prev,此时指向的元素是区间内比key大的,与刚刚cur的元素进行一个交换.再前移cur.此时区间内仍然保持着都比key大的性质
2.3.1双指针法代码实现:
void PartSort4(int* a, int left, int right)//双指针 { if(left>=right)return ; key=left; int prev=left,cur=left+1; while(cur<=right) { if(a[cur]<a[key]&&++prev!=cur) { swap(a[cur],a[prev]); } ++cur; } swap(a[prev],a[key]); PartSort4(a, left,prev-1); PartSort4(a, prev+1,right); }
2.4选取Key的方式:
介绍几种常用选择Key的方式.
2.4.1选择第一个:
当key选择第一个的时候,有可能会出现这个数就是这里面最小/最大的,若出现这种情况,则会让排序效率下降.
2.4.2选择中间:
同样会出现上述的情况.
2.4.3三数取中:
将left,right,medium(left+right/2)对应的三个数进行比较.之后将中间值放到Left位上即可.
int getMedium(int *a,int left,int right) { int medium=(left+right)>>1; if(a[left]>a[right]) { if(a[medium]>a[right]&&a[medium]<a[left]) return medium; else if(a[medium]<a[right]) return right; else return left; } //right>left else { if(a[medium]>a[left]&&a[medium]<a[right]) return medium; else if(a[medium]<a[left]) return left; else return right; } } //调用getmedium的格式 int key =getMedium(a,left,right); if(a[key]!=a[left])swap(a[key],a[left]);
完结撒花：
🌈本篇博客的内容【排序这样写才对Ⅱ -冒泡排序与快速排序Ⅰ】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
