qsort

如果是对于整型的排序，有冒泡排序法或选择排序法，那么若要排序浮点型，结构体等等，虽然我们能够写出若干个这样的函数来排列，但最终是不是都会过于复杂了？我们是否能够用一种函数来概括所有排序的情况？

答案当然是能够做到的。此时要用到系统自带的qsort（）函数。

那么什么又是qsort呢？

qsort基本介绍

在MSDN中查找，我们会发现qsort是库函数，采用的是快速排序法。且需要引入头文件<stdlib.h>来使用。在MSDN中，我们可以知道该函数的参数为下面代码所示：

void qsort( void *base,
            size_t num,
            size_t width, 
            int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

根据MSDN的解释我们能够知道每个参数的作用意义：

base——函数名（地址）
num——要排序的个数
width——每个元素所占的字节大小
elem1、elem2——是用来定位索要对比的两个元素大小的指针
int(* compare)(const void* elem1,const void* elem2)——用来比较的一个函数指针

void*

在了解qsort函数如何使用前，我们先理清这个平常并不太熟悉的指针类型——void* 型

void*的基本概念

void* 是一种无具体类型的指针，当我们创建了一个void*变量如：void* e1时，若在程序中写下*e1，程序会报错，指出非法的间接寻址。void*类型不能直接进行解引用操作，也不能直接进行+-操作。

正因为void是一种无类型指针，所以每种类型的地址我们都可以用void*指针来接收。

所以，由上面我们可以知道，利用void*能够接收所有类型的指针，从而void*是达到在qsort中使用能够接收所有类型的数据进行排序的前提。

void*的使用

强制类型转换——void接收到传入地址后我们可以通过强制类型转换来使用它。就那转换成int来举例：

int cmp_int(const void* elem1, const void* elem2)
{
  *(int*)elem1;//此时不会报错
  *(int*)elem2;
}
int main()
{
  int arr[] = { 0,4,2,5,8,9,1,3,7,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp_int);
  Print(arr, sz);
  return 0;
}

在我们将void*强制类型转换成int后，就可以当作是int*来使用了。

qsort的使用

在了解了void*后，我们还要知道qsort函数返回值返回的是什么，通过查看MSDN我们知道，若第一个元素小于第二个元素，则返回<0,若第一个元素等于第二个，则返回0，若第一个元素大于第二个元素，则返回>0。

所以在我们可以将cmp函数写出了，如下面代码所示：

int cmp_int(const void* elem1, const void* elem2)
{
  if (*(int*)elem1 < *(int*)elem2)
  {
    return -1;
  }
  else if (*(int*)elem1 > *(int*)elem2)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}
int main()
{
  int arr[] = { 0,4,2,5,8,9,1,3,7,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp_int);
  return 0;
}

因为要求的是返回值<、>或者=，所以也可以简化为：

int cmp_int(const void* elem1, const void* elem2)
{
  return *(int*)elem1 - *(int*)elem2;
}
int main()
{
  int arr[] = { 0,4,2,5,8,9,1,3,7,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp_int);
  return 0;
}

此时已经完善好了qsort的所有参数，也就相当于已经将我们要排序的数据已经全部排序好了，试着将所有元素打印出来：

#include <stdio.h>
void Print(int* arr, int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int cmp_int(const void* elem1, const void* elem2)
{
  return *(int*)elem1 - *(int*)elem2;
}
int main()
{
  int arr[] = { 0,4,2,5,8,9,1,3,7,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  //bubble_sort(arr, sz);
  qsort(arr, sz, sizeof(arr[0]), cmp_int);
  Print(arr, sz);
  return 0;
}

下面用结构体来使用qsort：

（比较名字）

int cmp_stu_name(const void* elem1, const void* elem2)
{
  return (strcmp((*(struct Stu*)elem1).name, (*(struct Stu*)elem2).name));
}

void print_stu(struct Stu* arr,int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%s %d %.2f", (*(arr+i)).name, (*(arr+i)).age, (*(arr+i)).score);
    printf("\n");
  }
}

int main()
{
  struct Stu arr[] = { {"Zhangsan",20,95.0f},{"Lisi",22,98.6f},{"Wangwu",15,78.9f} };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp_stu_name);
  print_stu(arr, sz);
  return 0;
}

(比较分数)

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct Stu
{
  char name[20];
  int age;
  float score;
};

void print_stu(struct Stu* arr, int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%s %d %.2f", (*(arr + i)).name, (*(arr + i)).age, (*(arr + i)).score);
    printf("\n");
  }
}

int cmp_stu_score(const void* elem1, const void* elem2)
{
  if ((*(struct Stu*)elem1).score<(*(struct Stu*)elem2).score)
  {
    return -1;
  }
  else if ((*(struct Stu*)elem1).score > (*(struct Stu*)elem2).score)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

int main()
{
  struct Stu arr[] = { {"zhangsan",20,85.4f},{"lisi",22,95.6f},{"wangwu",15,78.6f} };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp_stu_score);
  print_stu(arr, sz);
  return 0;
}

在知道了qsort是如何使用之后，我们不妨再深究探讨一个问题：为什么qsort要设计四个参数？我们是否有可以仿照qsort函数，写出一个属于自己的可以将任何类型排序的函数。

下面是经过了小绿长时间的研究后，写出的以冒泡排序法为原理的一串代码，成功仿照了qsort的功能：

#include <stdio.h>

swap(char* elem1, char* elem2, int width)
{
  int i = 0;
  for (i = 0; i < width; i++)
  {
    char str = *(elem1);
    *elem1 = *elem2;
    *elem2 = str;
    elem1++;
    elem2++;
  }
}

int cmp_int(const void* elem1, const void* elem2)
{
  if (*(int*)elem1 > *(int*)elem2)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

void q_bubble_sort(void* arr, int sz, int width, int (*cmp)(const void* elem1, const void* elem2))
{
  int i = 0;
  int j = 0;
  for (i = 0; i < sz-1; i++)
  {
    for (j = 0; j < sz - 1 - i; j++)
    {
      if (cmp((char*)arr+width*j, (char*)arr+width*(j+1)) > 0)
      {
        swap((char*)arr + width * j, (char*)arr + width * (j + 1),width);
      }
    }
  }
}

void print_int(int* arr, int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", *(arr + i));
  }
}

int main()
{
  int arr[] = { 0,4,2,5,8,9,1,3,7,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  q_bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
  print_int(arr, sz);
  return 0;
}

在这里我们要注意的是，我只写了排序int型数据的情况，而在排序前提类型时的cmp函数要重新写出来，才能使用。