【算法篇】排序——快速排序（c语言）

核心思想

• 排序算法的思想非常简单，在待排序的数列中，首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实可以随便选）。然后把这个待排序的数列中小于基准数的元素移动到它的左边，大于它的移到右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别重复上述步骤，直到各个分区只有一个数时为止。

代码示例

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void quick_sort(int l, int r)
{
    int mid = in[(l + r) / 2];//这里是选择中间值作为基准
    int i = l, j = r;
    do
    {
        while (in[i] < mid)
            i++; //找到左边比基准值大的数的位置
        while (in[j] > mid)
            j--; //找右边小的
        if (i <= j)
        {
            swap(&(in[i]), &(in[j])); //交换使左边的小右边的大
            i++;
            j--;
        }
    } while (i <= j);
    if(l<j)
        quick_sort(l, j);//排左边
    if(r>i)
        quick_sort(i, r);//排右边
}

当然了一般情况下不用自己写（毕竟有现成的）
来看一下炒鸡好用的qsort函数

qsort函数的用法

函数声明

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void , const void))

参数说明

base-- 指向要排序的数组的第一个元素的指针。
nitems-- 由 base 指向的数组中元素的个数。
size-- 数组中每个元素的大小，以字节为单位。
==compar-- 用来比较两个元素的函数，即函数指针（回调函数）==

• compar函数的形式决定了对谁排序*

int compar(const voidp1, const voidp2);

compar函数的返回值	描述
<0	p1所指向元素将被排在p2所指向元素的左面
=0	p1所指向元素与p2所指向元素的顺序不确定
>0	p1所指向元素会被排在p2所指向元素的右面

具体用法说明

• 对一维数组

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

• 对二维数组

int comp(const void*a,const void*b)
{
    return ((int*)a)[0]-((int*)b)[0];
} 

• 对字符串

int Comp(const void*p1,const void*p2)
{
    return strcmp((char*)p2,(char*)p1);
}
int main()
{
    char a[MAX1][MAX2];
    initial(a);
    qsort(a,lenth,sizeof(a[0]),Comp);
    //lenth为数组a的长度 
}

• 对结构体一级排序

struct Node
{
    double data;
    int other;
}s[100];
int Comp(constvoid*p1,constvoid*p2)
{
    return(*(Node*)p2).data>(*（Node*）p1).data?1:-1;
}
qsort(s,100,sizeof(s[0]),Comp);

• 对结构体多级排序

struct Node
{
    int x;
    int y;
}s[100];
//按照x从小到大排序，当x相等时按y从大到小排序
int Comp(const void*p1,const void*p2)
{
    struct Node*c=(Node*)p1;
    struct Node*d=(Node*)p2;
    if(c->x!=d->x)returnc->x-d->x;
    else return d->y-c->y;
}

• 对结构体的字符串

struct Node
{
    int data;
    char str[100];
}s[100];
//按照结构体中字符串str的字典序排序
int Comp(const void*p1,const void*p2)
{
    return strcmp((*(Node*)p1).str,(*(Node*)p2).str);
}
qsort(s,100,sizeof(s[0]),Comp);