【排序】排序这样写才对Ⅱ -冒泡排序与快速排序Ⅰ网站首页 技术交流

【排序】排序这样写才对Ⅱ -冒泡排序与快速排序Ⅰ

ppeua 2023-05-19 04:00:04

简介【排序】排序这样写才对Ⅱ -冒泡排序与快速排序Ⅰ

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]);