qsort的相关总结

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )

qsort位于

参数说明：
第一个参数 代表数组的首地址，通常直接写数组名即可
第二个参数 是要排序的数组个数
第三个参数 是每个元素的大小 通常sizeof(s[0])
第四个参数 是自定义比较函数 (实现升序降序)

需要注意的地方:
int compare (const void *elem1, const void *elem2 ) ); 
campare 这个函数名字可以任意写，但是函数的返回值类型必须是int 以及参数列表的类型必须是 const void *

No.1手动实现快速排序

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 110
using namespace std;

int a[N];

void Swap(int &a, int &b)
{//这一部分也没必要手动实现完全可以使用头文件<algorithm>中的swap函数
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void QuickSort(int start, int end)
{
    int k=a[start];
    int i=start, j=end;
    if(start >= end)
        return ;
    while(i != j)
    {
        while( i<j && a[j]>=k)
            j--;
        Swap(a[j], a[i]);
        while( i<j && a[i]<=k)
            i++;
        Swap(a[i], a[j]);
    }
    QuickSort(start, i-1);
    QuickSort(i+1, end);
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);

    QuickSort(0, n-1);

    for(int i=0; i<n; i++)
        printf("%d ", a[i]);
    return 0;
}

No.2 对int数组排序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int s[10000],n,i;

int cmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);//实现升序排列
}

int main()
{
     scanf("%d",&n);
     for(i=0;i<n;i++) scanf("%d",&s[i]);

     qsort(s,n,sizeof(s[0]),cmp);

     for(i=0;i<n;i++) printf("%d ",s[i]);

     return(0);
}

No.3 对double

注意： 要判断如果a==b返回0的,但是严格来说,两个double数是不可能相等的,
只能说fabs(a-b)<1e-20之类的这样来判断,所以这里只返回了1和-1

#include <stdio.h>
#include <stdlib.h>

double s[1000];
int i,n;

int cmp(const void * a, const void * b)
{
     return((*(double*)a-*(double*)b>0)?1:-1);//升序排列
}

int main()
{
     scanf("%d",&n);
     for(i=0;i<n;i++)
        scanf("%lf",&s[i]);

     qsort(s,n,sizeof(s[0]),cmp);

     for(i=0;i<n;i++)
        printf("%.2f ",s[i]);

     return 0;
}

No.4对一维char数组中的字符排序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char s[10000],i,n;

int cmp(const void *a,const void *b)
{
     return(*(char *)a-*(char *)b);//升序排列
}

int main()
{
     scanf("%s",s);
     n=strlen(s);
     qsort(s,n,sizeof(s[0]),cmp);

     printf("%s",s);
     return(0);
}

No.5对结构体的排序

//QAQ 其实原本只是打算查一下结构体怎么排序，没想到把一整套的东西都给复习了一遍
好吧…..不说废话了，结构体排序需要注意的是，当进行类型强制转换的时候不要直接在return 进行，别问我是怎么知道的TAT

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node
{
    int no;
    int data;
}STU[100];

int cmp(const void *a, const void *b)
{
    struct Node *p1, *p2;//单独定义
    p1 = (struct Node *)a;
    p2 = (struct Node *)b;
    return ((p1->data) - (p2->data));//升序排列
}

int main()
{
     int n;
     scanf("%d", &n);
     for(int i=0; i<n; i++)
     {
         STU[i].no = i+1;
         scanf("%d", &STU[i].data);
     }

     qsort(STU, n, sizeof(STU[0]), cmp);

     for(int i=0; i<n; i++)
     {
         printf("%d    %d\n", STU[i].no, STU[i].data);
     }
     return 0;
}

No.6对结构体的二重排序(指定两个变量作为排序的依据)

其实更多重的排序也是如此，不过是else if

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node
{
    int no;
    int data;
}STU[100];

int cmp(const void *a, const void *b)
{
    struct Node *p1, *p2;
    p1 = (struct Node *)a;
    p2 = (struct Node *)b;
    if((p1->data) != (p2->data))
        return ((p1->data) - (p2->data));
    else
        return ((p1->no) - (p2->no));
}

int main()
{
     int n;
     scanf("%d", &n);
     for(int i=0; i<n; i++)
     {
         STU[i].no = i+1;
         scanf("%d", &STU[i].data);
     }

     qsort(STU, n, sizeof(STU[0]), cmp);

     for(int i=0; i<n; i++)
     {
         printf("%d    %d\n", STU[i].no, STU[i].data);
     }
     return 0;
}

No.7 二维字符数组的排序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char s[100][100];

int cmp(const void *a, const void *b)
{
    return (strcmp((char *)a, (char *)b ));
}

int main()
{
     int n;
     scanf("%d", &n);
     for(int i=0; i<n; i++)
        scanf("%s", s[i]);

     qsort(s, n, sizeof(s[0]), cmp);

     for(int i=0; i<n; i++)
        printf("%s\n", s[i]);
     return 0;
}

No.8 指针数组的排序

两个地方写的特别巧妙：
1.cmp 函数中的 return (strcmp( (char )a, (char )b)) //巧妙的难以叙述
2.动态申请内存时候直接写
s[i] = (char )malloc(sizeof(char )) //666

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *s[100];

int cmp(const void *a, const void *b)
{
    return(strcmp( *(char **)a, *(char **)b ));
}

int main()
{
     int n;
     scanf("%d", &n);
     for(int i=0; i<n; i++)
     {
         s[i] = (char *)malloc(sizeof(char *));
         scanf("%s", s[i]);
     }

     qsort(s, n, sizeof(s[0]), cmp);

     for(int i=0; i<n; i++)
        printf("%s\n", s[i]);
     return 0;
}