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