快速排序(详解)
描述:
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序 的平均时间复杂度为O(NlogN),是冒泡排序的一种改进版。
方法:快速排序主要采用“二分”的思想,步骤如下:
1) 设置两个变量i、j，排序开始的时候：i=0，j=n-1；
2）第一个数组值作为比较值，首先保存到temp中，即temp=A[0]；
3）然后j-- ,向前搜索,找到小于temp后,因为s[i]的值保存在temp中,所以直接赋值,s[i]=s[j]
4）然后i++,向后搜索,找到大于temp后,因为s[j]的值保存在第2步的s[i]中,所以直接赋值,s[j]=s[i],然后j--,避免死循环
5）重复第3、4步，直到i=j,最后将temp值返回s[i]中
6) 然后采用“二分”的思想,以i为分界线,拆分成两个数组 s[0,i-1]、s[i+1,n-1]又开始排序
如下图,以数组 6 4 7 1 2为例:
代码如下:
#include "stdio.h"
void find_frst(int *s,int lift,int right)
{
int i=lift,j=right,temp; //(1)初始化i、j
if(lift>=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,lift,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 lift,int right)
{
int i=lift,j=right,temp; //(1)初始化i、j
if(lift>=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,lift,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;
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);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-09-26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读