快速排序之C语言实现

作者 : 开心源码 本文共2014个字,预计阅读时间需要6分钟 发布时间: 2022-05-13 共287人阅读

具体代码

#include<stdio.h>//定位int Patrition(int* R, int start, int end){    int standard = R[start];        int i = start;    int j = end;        //寻觅恰当位置(下文会细讲这里)    while(i!=j)    {        while(i<j&&R[j]>=standard)  j--;                if(i<j&&R[j]<standard)        {            R[i] = R[j];            i++;        }                while(i<j&&R[i]<=standard)  i++;                if(i<j&&R[i]>standard)        {            R[j] = R[i];            j--;        }       }    R[i] = standard;    return i;   }//这里统一用物理位置来表示 void QuickSort(int* R, int start, int end){       if(start<end)    {        int index = Patrition(R,start,end);        QuickSort(R,start,index-1);          QuickSort(R,index+1,end);    }   }int main(){    int M[6] = {9,5,3,7,8,4};       QuickSort(M,0,5);    for(int i=0;i<6;i++)    {        printf("%d  ", M[i]);       }}

过程分析

快速排序的本质,说白了就是,在一个数组中,把某个数按照大小顺序放到正确的位置,将数组分为两个小的数组。如此操作,直到每个数都在自己正确的位置。

快速排序主要由两个部分组成:
1.排序操作(QuickSort),通过递归的方式,得到有序的排列。其内部工作原理就是先将数组中的一个元素定位,分为两小个,再将两小数组排序,最后整个数组就是有序的了。(另外若数组被划分为只有一个元素的情况,则直接返回)

2.定位操作(Patrition),通过一一比照的方式,将这个数放置到正确的位置(比方A元素在数组中是第4小,那么A元素就会被放置到4号位置去)。这样一轮操作之后,这个数的左边全是小于它的,右边全是大于它的。(但是顺序不肯定对)

比方说对下面这个数组的排序:

image.png

当我们调用QuickSort函数的时候,则会依次发生Patrition(定位)和两次对划分后的小数组的QuickSort操作。

Patrition操作

结合代码和图,我一步一步分析:

第一步,选择目标(也就是你要给哪个元素找到对应位置,这里我选的是首个元素)

int standard = R[start];

image.png

第二步, 准备从两侧依次对数组进行遍历,所以把指针准备好:

int i = start;
int j = end;

image.png

第三步,核心步骤,寻觅正确位置:

在i和j相遇之前,一一挑选元素,若是大于基准,则放到右边去,若是小于基准,则放到左边去。

while(i!=j)
{…..}

不过需要注意的是,放元素的位置不能使原数组的数据丢失。
一开始,第一个位置的元素5已经被作为基准了,所以第一个位置现在是空的,可以存放元素。
按要求,需要从右边开始,把比基准小的元素放过来,现在j指针指的3就符合条件,所以,移动。

image.png

现在,j的内容被写了,所以现在j指针对应的位置是可写的,于是从右边开始寻觅有没有比基准大的?
很显然,7就是,所以7移过去

image.png

现在又应该从右边开始找了,于是乎,0也符合条件,写到i指针所指的7的位置去。

image.png

现在可写的位置到右边去了,所以右边继续找比基准大的:

image.png

现在又该j指针动了,6比5大,不论。4比5小,写过去!

image.png

现在i指针动起来,2可以,过!1可以,也过!

当i指到4的时候,i指针和j指针相遇了,说明这其实就是基准元素5应该在的位置,所以把5写过来。

image.png

定位完成!

我再补充一下代码里的每一步的作用:

    while(i<j&&R[j]>=standard)  j--;    //右指针,假如大于基准条件,就一直向左走            if(i<j&&R[j]<standard)          //假如小了,那么就把元素写过去    {                               //Ps.另外一边的指针的位置        R[i] = R[j];                //永远是指的可写的        i++;                        //所以直接R[i] = R[j]    }            while(i<j&&R[i]<=standard)  i++;//左指针,假如大于基准条件,就一直向左走            if(i<j&&R[i]>standard)          //假如大了,写过去    {        R[j] = R[i];        j--;    }       //继续循环直到i==j  (这一堆代码都在while里)   

第四步,把值放到对应的位置(对应上面最后一幅图)

R[i] = standard;

第五步,返回这个基准的位置,代表两边已经被分化好了,接下来分别对两边的数组进行QuickSort就可

return i;

QuickSort

承接上面的图:

image.png

分别再对两边的数组进行同样的操作就可。

image.pngimage.png

排序成功!

性能分析

image.png

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 快速排序之C语言实现

发表回复