qsort 订阅
qsort函数C语言编译器函数库自带的排序函数。qsort 的函数原型是void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*)); 是base所指数组进行排序。qsort函数包含在C 标准库 - 中。 [1] 展开全文
qsort函数C语言编译器函数库自带的排序函数。qsort 的函数原型是void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*)); 是base所指数组进行排序。qsort函数包含在C 标准库 - 中。 [1]
信息
头文件
stdlib.h
功 能
使用排序例程进行排序
类    型
标准库函数
中文名
qsort
应    用
C编程
外文名
qsort
qsort函数简介
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))回调函数:回调函数就是一个通过函数指针调用的函数。如果把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,就说这是回调函数。 [2]  compar参数compar参数指向一个比较两个元素的函数。比较函数的原型应该像下面这样。注意两个形参必须是const void *型,同时在调用compar 函数(compar实质为函数指针,这里称它所指向的函数也为compar)时,传入的实参也必须转换成const void *型。在compar函数内部会将const void *型转换成实际类型。int compar(const void *p1, const void *p2);如果compar返回值小于0(< 0),那么p1所指向元素会被排在p2所指向元素的左面;  如果compar返回值等于0(= 0),那么p1所指向元素与p2所指向元素的顺序不确定;  如果compar返回值大于0(> 0),那么p1所指向元素会被排在p2所指向元素的右面。 [2]  使用排序例程进行排序。该函数不返回任何值。头文件:stdlib.h;
收起全文
精华内容
下载资源
问答
  • Qsort

    2020-11-18 21:20:48
    思路:将第一次Qsort单独列出来,因为只有第一次的pivot取值与Qsort函数中对于pivot的取值是不同的。 整体来讲需要写3个函数: Qsort函数,取pivot将其放在需要比较的数组的最后一个(也就是原数组的倒数第二个,...

    在这里插入图片描述
    在这里插入图片描述
    思路:将第一次Qsort单独列出来,因为只有第一次的pivot取值与Qsort函数中对于pivot的取值是不同的。
    整体来讲需要写3个函数:
    Qsort函数,取pivot将其放在需要比较的数组的最后一个(也就是原数组的倒数第二个,因为原数组的最后一个在取pivot的时候已经比较完成,其值一定大于pivot),i从第二个数开始后移(原数组的第一个数在取pivot时也已经完成比较,一定比pivot小),如果大于pivot则停下,j从pivot所处位置的前一个开始前移(也就是原数组的倒数第三位),如果小于pivot就停下;如果i<j,则交换,否则将i相对应的数的大小与pivot相比较,更大的放在原数组的倒数第二位上
    Median3函数:选择数组的首位,末位,中间位,相互比较大小,去中间值为pivot,并将其按照大小顺序以此放在数组首位、末位、倒数第二位上,便于后续调用数据
    Insertionsort函数:在数据量较小时,使用插入排序会快于qsort
    其他具体解释在代码里:

    #include <stdio.h>
    #include <stdlib.h>
    
    void Qsort(int *number, int left, int right);
    int Median3(int *number,int left, int right);
    void Insertionsort(int *number, int left, int N);
    
    int main()
    {
        int number[11];
        int n;
        int pivot;
        int temp;
        int left=0;
        int right=9;
        int i,j;
        scanf("%d",&n);//由题,n为给定的第一次排序的pivot//
        number[0]=49;
        number[1]=38;
        number[2]=65;
        number[3]=97;
        number[4]=76;
        number[5]=13;
        number[6]=27;
        number[7]=50;
        number[8]=2;
        number[9]=8;
        number[10]=0;
        pivot = number[n];//将第一次的pivot与末位交换//
        number[n]=number[right];
        number[right]=pivot;
        if(left+3<=right)//如果数据量可以使用Qsort//
        {
            printf("Qsort(%d,%d):",left,right);
            i=left-1;//第一次排序的特殊点在于给定了pivot,我们还没有比较它和首位的大小,所以这里的i是从-1开始的(后续我们需要使用++i)//
            j=right;//原因同上,j从最后一个开始,因为要使用--j//
            for(; ;)
            {
                while(number[++i]<pivot){}
                while(number[--j]>pivot){}
                if(i<j)
                {
                    temp=number[i];
                    number[i]=number[j];
                    number[j]=temp;
                }
                else
                {
                    break;
                }
            }
            if(pivot<number[i])//找到pivot所处的位置//
            {
                temp=number[i];
                number[i]=number[right];
                number[right]=temp;
            }
        }
        for(int d=0;d<10;d++)
        {
            printf("%d,",number[d]);
        }
        printf("\n");
        //printf("here:%d:::",i-1);
        Qsort(number,left,i-1);//左侧排序//
        //printf("now:");
        Qsort(number,i+1,right);//右侧排序//
        
        return 0;
        
        
    }
    int Median3(int *number,int left, int right)
    {
        int center=(left+right)/2;
        int temp;
        if(number[left]>number[center])
        {
            temp=number[left];
            number[left]=number[center];
            number[center]=temp;
        }
        if(number[left]>number[right])
        {
            temp=number[left];
            number[left]=number[right];
            number[right]=temp;
        }
        if(number[center]>number[right])
        {
            temp=number[center];
            number[center]=number[right];
            number[right]=temp;
        }
        temp=number[center];
        number[center]=number[right-1];
        number[right-1]=temp;
        
        return number[right-1];
    }
    
    void Qsort(int *number, int left, int right)
    {
        int i,j;
        int temp;
        int pivot;
        if(left+3<=right)
        {
            pivot=Median3(number,left,right);
            i=left;
            j=right-1;
            for(; ;)
            {
                while(number[++i]<pivot){}
                while(number[--j]>pivot){}
                if(i<j)
                {
                    temp=number[i];
                    number[i]=number[j];
                    number[j]=temp;
                }
                else
                {
                    break;
                }
            }
            if(pivot<number[i])
            {
                temp=number[i];
                number[i]=number[right-1];
                number[right-1]=temp;
            }
            printf("Qsort(%d,%d):",left,right);
            for(int k=0;k<10;k++)
            {
                printf("%d,",number[k]);
            }
            printf("\n");
            Qsort(number,left,i-1);
            Qsort(number,i+1,right);
        }
        else
        {
            if(left==right)
            {
                printf("insert(%d,%d):",left,right-left+1);
                for(int k=0;k<10;k++)
                {
                    printf("%d,",number[k]);
                }
                printf("\n");
            }
            else
            {
                Insertionsort(number,left,right-left+1);
            }
            
        }
    }
    void Insertionsort(int *number, int left, int N)
    {
        int j,p;
        int tmp;
        for(p=left+1;p<N+left;p++)
        {
            tmp=number[p];
            for(j=p;j>left&&number[j-1]>tmp;j--)
            {
                number[j]=number[j-1];
            }
            number[j]=tmp;
        }
        printf("insert(%d,%d):",left,N);
        for(int k=0;k<10;k++)
        {
            printf("%d,",number[k]);
        }
        printf("\n");
    }
    
    展开全文
  • qsort

    2020-05-04 09:33:11
    C++中有很方便很实用的函数sort,但是对于刚刚学习写C语言的人来说,可能会有一些障碍,所以写个博客来解释一下C中的排序函数qsort,之后也会另发博客来解释sort函数 本文仅用于给刚刚接触不久C语言的人解释qsort...

    C++中有很方便很实用的函数sort,但是对于刚刚学习写C语言的人来说,可能会有一些障碍,所以写个博客来解释一下C中的排序函数qsort,之后也会另发博客来解释sort函数
    本文仅用于给刚刚接触不久C语言的人解释qsort函数,各位大佬可以忽略本文
    先上示例代码

    //使用qsort函数(从小到大排序)
    #include<stdio.h>
    #include<stdlib.h>

    int n,i,a[10000];

    int comp(const void a,const void b)
    {
    if(
    (int
    )a>(int)b)return 1;
    else return -1;
    }

    int main()
    {
    scanf("%d",&n);
    for (i=0; i<n; i++)
    {
    scanf("%d",&a[i]);
    }
    qsort(a, n, sizeof(int), comp);
    for (i=0; i<n; i++)
    {
    printf("%d ",a[i]);
    }
    return 0;
    }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    

    输入:

    10
    2 3 4 5 6 1 7 8 9 0

    1
    2
    

    输出:

    0 1 2 3 4 5 6 7 8 9

    1
    

    qsort函数原型

    //qsort位于<stdlib.h>头文件下
    void qsort(voidbase,size_t num,size_t width,int(__cdeclcompare)(const void*,const void*));

    1
    2
    

    参数列表

    voidbase //需要排序的数组首地址
    size_t num //需要排序的长度
    size_t width //每一个需要进行排序的元素的大小
    int(__cdecl
    compare)(const void*,const void*)//自己写的排序函数,输入的是两个void类型的指针

    1
    2
    3
    4
    

    示例代码分析

    示例中,要排序的数组为a,排序长度为n,每个元素都为int,所以大小为sizeof(int),使用的排序函数是自己写的comp函数。
    关于“comp”函数写法

    1、首先,这是一个int类型的函数,函数名可以自己取,参数列表为两个void类型的指针。(前面的const的意思是常量,关于为什么要加const,既然默认了看本文的以小白为主,那么在本文就不具体解释。不加const部分编辑器会报warning但不会error,不加也可以正常使用,但是为了解决强迫症的0 warning和0 error的目标,这里给出解决办法)
    所以这个函数内,需要对这两个参数进行强制转换。(例如使用(int*)a这样的结构)
    2、其次,输入的是指针,所以需要利用指针去取参数(示例中再对int类型的指针取值)
    3、函数的返回值是int类型的值,具体的关于返回的值对排序的影响这里不做讨论,可以参照示例去写,情况只有返回值大于0、返回值小于0、返回值等于0三种情况,所以,可以把comp函数中的 “>” 改成 “<” 即可完成从大到小排序。当然也可以进一步缩减,使得函数直接返回a和b的差值。如下:

    int comp(const void a,const void b)
    {
    return (
    (int
    )a-(int)b);
    }

    1
    2
    3
    4
    

    当然,如果有能力使用sort的人,建议还是不要使用qsort函数。因为参数和自定义函数这么多

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,944
精华内容 2,777
关键字:

qsort