快速排序(详解)

描述:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

快速排序 的平均时间复杂度为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);
    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

C++ STL学习之容器set和multiset (补充材料)

一、set和multiset基础 set和multiset会根据特定的排序准则,自动将元素进行排序。不同的是后者允许元素重复而前者不允许。 ? 需要包含头文件:...

3428
来自专栏用户画像

7.2.1 直接插入排序

插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列,直到全部记录插入完成。

772
来自专栏python学习指南

python字典

本篇将介绍Python里面的字典,更多内容请参考:Python学习指南 Python是什么? Python内置了字典dict的支持,dict全称dicti...

1928
来自专栏人工智能LeadAI

为什么算法容易忘记之快速排序

本文用来帮助大家理解记忆快速排序,方法和上篇文章一样,着重理解算法基本思想及其代码中的循环控制变量的意义。 基本思想 快速排序属于拿着元素找位置的算法。思路非常...

3334
来自专栏小樱的经验随笔

KMP算法学习(详解)

kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简...

2595
来自专栏nummy

numpy入门

numpy中最主要的对象是同质数组array,也就是说数组中的元素类型都是一样的。数组的维度也称之为axis,axis的的个数称之为秩rank。

702
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

1501
来自专栏null的专栏

MATLAB技巧——sort和sortrows函数

1、sort函数 sort函数用于对数据进行排序,通过help sort命令,可以查找到sort函数的具体用法: Y = SORT(X,DIM,MODE) ha...

2815
来自专栏GAN&CV

python lambda表达式的介绍和使用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_25737169/article/d...

741
来自专栏老司机的技术博客

golang学习笔记8:控制结构

关键字 if 和 else 之后的左大括号 { 必须和关键字在同一行,如果你使用了 else-if 结构,则前段代码块的右大括号 } 必须和 else-if 关...

543

扫码关注云+社区