Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

0.常见的排序算法:

1.冒泡排序:

1.1冒泡排序代码实现:

1.2冒泡排序代码优化:

2.快速排序:

​编辑2.1Hore法:

2.2挖坑法:

 2.2.1挖坑法代码实现:

2.3双指针法:

2.3.1双指针法代码实现:        

2.4选取Key的方式:

2.4.1选择第一个:

2.4.2选择中间:

2.4.3三数取中:

完结撒花：

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;elsereturn right;}
}
//调用getmedium的格式
int key =getMedium(a,left,right);if(a[key]!=a[left])swap(a[key],a[left]);

完结撒花：

🌈本篇博客的内容【排序这样写才对Ⅱ -冒泡排序与快速排序Ⅰ】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！