快速排序(详解)
2018-06-18 03:58:57来源:未知 阅读 ()
描述:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序 的平均时间复杂度为O(NlogN),是冒泡排序的一种改进版。
方法:快速排序主要采用“二分”的思想,步骤如下:
如下图,以数组 6 4 7 1 2为例:
代码如下:
#include "stdio.h" void find_frst(int *s,int left,int right) { int i=left,j=right,temp; //(1)初始化i、j if(left>=right) return ; temp=s[i]; //(2)以第一个数组为比较值,保存到temp中 while(i<j) { while(j>i&&s[j]>=temp) //(3)j--,找小值 j--; s[i]= s[j]; //保存小值,到s[i]上 while(i<j&&s[i]<=temp) //(4)i++,找大值 i++; s[j--]=s[i]; //保存大值 到s[j]上 } s[i]=temp; //(5)将比较值放在s[i]上 /*(6)拆分成两个数组 s[0,i-1]、s[i+1,n-1]又开始排序 */ find_frst(s,left,i-1); //左 find_frst(s,i+1,right); //右 } int main() { int i=0,s[100],n; scanf("%d",&n); //输入数组长度 for(i=0;i<n;i++) scanf("%d",&s[i]); find_frst(s,0,n-1); for(i=0;i<n;i++) printf("%d ",s[i]); //打印 printf("\n"); }
既然有了排序,那么还有可能用到查找,在有序条件下,当然用二分查找快咯,即简单又速度快
代码如下:
#include "stdio.h" /*快速排序 */ void find_frst(int *s,int left,int right) { int i=left,j=right,temp; //(1)初始化i、j if(left>=right) return ; temp=s[i]; //(2)以第一个数组为比较值,保存到temp中 while(i<j) { while(j>i&&s[j]>=temp) //(3)j--,找小值 j--; s[i]= s[j]; //保存小值,到s[i]上 while(i<j&&s[i]<=temp) //(4)i++,找大值 i++; s[j--]=s[i]; //保存大值 到s[j]上 } s[i]=temp; //(5)将比较值放在s[i]上 /*(6)拆分成两个数组 s[0,i-1]、s[i+1,n-1]又开始排序 */ find_frst(s,left,i-1); //左 find_frst(s,i+1,right); //右 } /*二分查找 *s[]:数组 size:数组个数 cmp:需要比较的数字 *返回值:表示数组的第几个,返回-1表示没有找到 */ int binary_query(const int* s, int size, int cmp) { int low = 0; int high = size-1; int mid; //中间值 while(low<=high) { mid = (low+high)/2; if(s[mid] == cmp) return mid; else if(s[mid] > cmp) high = mid-1; else low = mid+1; } return -1; }
int main() { int i=0,s[100],n,tmp,index; scanf("%d",&n); //输入:数组长度 for(i=0;i<n;i++) scanf("%d",&s[i]); //输入:数组数据 find_frst(s,0,n-1); printf("find_frst:\n",s[i]); for(i=0;i<n;i++) printf("%d ",s[i]); //打印:有序数组 printf("\n"); scanf("%d",&tmp); //输入:要查找的数据 index=binary_query(s,n,tmp); if(index<0) printf("ERR,The value is not querying\n"); else printf("index=%d\n",index); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:【C语言程序】输出前50个素数
下一篇:JPEG流封装AVI视频
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 前缀和 2020-05-04
- 二叉排序树 2020-05-02
- 快速批量将B站 BV 号更改为 AV 号 - BTA 2020-04-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash