『C语言进阶』qsort函数及模拟实现

简介: 『C语言进阶』qsort函数及模拟实现

前言

在上篇指针进阶中,我们对函数指针、函数指针数组、函数指针数组指针以及回调函数有了一定的了解,文章末尾简单的对qsort函数进行了展示,今天我们主要以qsort函数用冒泡排序的模拟实现以及各种类型的排序,后面针对指针和数组一些细节上的讲解~

一、qsort函数介绍

qsort是一个库函数,快速排序的方法来实现的, 头文件是<stdlib.h>

qsort库函数:

void qsort( void *base, size_t num, size_t size, int (*compare )(const void *, const void *) );

传入的参数,一个是指针,一个整形,一个整形,一个函数指针;

base 数组首元素(就是数组名),num数组里有多少个元素,size每个元素的大小(单位是字节),compare指向数组中比较方式的函数指针;

功能介绍:

使用函数确定顺序,对指向的数组的元素进行排序,每个元素的长度以字节为单位。

此函数使用的排序算法通过调用指定的函数(要自己定义元素比较方式函数传给qsort)并将指向元素的指针作为参数来比较元素.

该函数不返回任何值,而是通过按定义重新排序数组元素来修改指向的数组的内容。


二、qsort函数的应用

由于使用qsort函数时,并不知道要排序的元素是什么类型,这时需要写一个compare函数,并对立面的参数强制类型转化

2.1 整型数组排序

#include<stdio.h>
#include<stdlib.h>
void Print(int arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
}
int com_int(const void* e1, const void* e2)
{
  return *(int*)e1 - *(int*)e2;
}
int main()
{
  int arr[] = { 1,3,7,5,8,9,0,2,4,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), com_int);
  Print(arr, sz);
  return 0;
}

运行结果:

0 1 2 3 4 5 6 7 8 9

2.2 浮点型数组排序

#include <stdio.h>
#include <stdlib.h>
void Print(double arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%2.2lf ", arr[i]);
  }
}
int com_double(const void* e1, const void* e2)
{
  return *(double*)e1 - *(double*)e2;
}
int main()
{
  double arr[6] = { 8.26, 65.5, 73.53,  43.45,  95.3, 19.5 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), com_double);
  Print(arr, sz);
  return 0;
}

运行结果:

8.26 19.50 43.45 65.50 73.53 95.30

2.3 字符型排序

#include <stdio.h>
#include <stdlib.h>
void Print(char arr[],int sz)
{
  for (int i = 0; i < sz; i++)
    printf("%c ", arr[i]);
}
int char_sort(const void* e1, const void* e2)
{
  return (*(char*)e1) - (*(char*)e2);
}
int main()
{
  char arr[10] = { 'd','g','b','a','e','i','h','c','j','f' };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), char_sort);
  Print(arr, sz);
  return 0;
}

运行结果:

a b c d e f g h i j

2.4 结构体数组排序

#include <stdio.h>
#include <stdlib.h>
typedef struct student
{
  char name[15];
  int age;
  float score;
}S;
void Print(struct student* stu,int sz)
{
  for (int i = 0; i < sz; i++)
  {
    printf("%-12s %-5d %-5.2fm\n", stu[i].name, stu[i].age, stu[i].score);
  }
}
int com_age(const void* e1, const void* e2)
{
  return (((S*)e1)->age - ((S*)e2)->age);
}
int com_score(const void* e1, const void* e2)
{
  return ((S*)e1)->score - ((S*)e2)->score;
}
int com_name(const void* e1, const void* e2)
{
  return strcmp(((S*)e1)->name, ((S*)e2)->name);
}
int main()
{
  S stu[5] = { {"chu jie niu",20,1.73f},
      {"xiao wang",19,1.68f},
      {"qing niao",21,1.59f},
      {"wao shu li",16,1.83f},
    {"peng hu wan",15,1.81f} };
  int sz = sizeof(stu) / sizeof(stu[0]), input = 0;
  qsort(stu, sz, sizeof(stu[0]), com_age);
  printf("姓名      年龄   身高\n");
  Print(stu, sz);
  return 0;
}

运行结果:

姓名        年龄   身高
peng hu wan  15    1.81 m
wao shu li   16    1.83 m
xiao wang    19    1.68 m
chu jie niu  20    1.73 m
qing niao    21    1.59 m

三、qsort模拟实现(冒泡排序)

3.1 冒泡排序

#include <stdio.h>
void Print(int arr[], int sz)
{
  for (int i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
}
void bubble_sort(int arr[],int sz)
{
  int i = 0;
  for (i = 0; i < sz - 1; i++)
  {
    int j = 0;
    for (j = 0; j < sz - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
}
int main()
{
  int arr[] = { 5,3,7,6,1,8,9,2,4,0 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  bubble_sort(arr,sz);
  Print(arr, sz);
  return 0;
}

3.2 qsort模拟实现

第一步:冒泡函数的参数

首先要修改的是冒泡排序函数的参数

void bubble_sort(void* arr,size_t num,size_t width,int(*compare)(const void*,const void*))

需要注意的是qsort函数事先是不知道传过来的数组是什么类型,所以都先用void*接受

第二步:比较元素的方法

在对两元素比较时,事先是不知道类型的

  1. 要先将arr强制类型转化为char*,因为一个字节是类型的最小单位,这时候就需要用到width了
  2. 元素的比较方式不再是单一的相减,这里用到自定义函数,元素的比较方式函数

if(cmp((char*)arr+jwidth),(char)arr+(j+1)*width)>0)

第三步:交换函数

修改为char*类型进行交换

swap(char* e1, char* e2, int width)
{
  int i = 0;
  char p = 0;
  for (i = 0; i < width; i++)
  {
    p = *(e1 + i);
    *(e1 + i) = *(e2 + i);
    *(e2 + i) = p;
  }
}

注意:

void*可以接受任何类型的变量,但是并不能直接使用,要强制类型转化为对应类型使用

代码展示:

#include <stdio.h>
void Print(int arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
}
void swap(char* e1, char* e2, int width)
{
  int i = 0;
  char p = 0;
  for (i = 0; i < width; i++)
  {
    p = *(e1 + i);
    *(e1 + i) = *(e2 + i);
    *(e2 + i) = p;
  }
}
void bubble_sort(void* base, int sz, int width, int (*cmp)(const void* e1, const void* e2))
{
  int i = 0;
  int j = 0;
  for (i = 0; i < sz; i++)
  {
    for (j = 0; j < sz - 1 - i; j++)
    {
      if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
      {
        swap((char*)base + j * width, (char*)base + (j + 1) * width, width);//一个字节一个字节的交换
      }
    }
  }
}
int com_int(const void* e1, const void* e2)
{
  return *(int*)e1 - *(int*)e2;
}
int main()
{
  int arr[] = { 1, 3, 6, 2, 0, 9, 4, 8, 5, 7 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  bubble_sort(arr, sz, sizeof(arr[0]), com_int);
  Print(arr, sz);
  return 0;
}

qsort函数用冒泡排序的模拟实现就讲到这里,指针的进阶也到此结束了,接下来对指针和数组一些细节上的补充到时候会在文章见分晓,欢迎大家互三,一起交流,互相学习~~

相关文章
|
20小时前
|
存储 开发框架 编译器
C语言进阶—自定义类型:结构体,枚举,联合
C语言进阶—自定义类型:结构体,枚举,联合
|
20小时前
|
算法 编译器 C语言
|
1天前
|
安全 编译器 C语言
【C语言】字符串和内存函数的介绍 -- 详解
【C语言】字符串和内存函数的介绍 -- 详解
|
1天前
|
算法 编译器 C语言
【C语言】函数和递归
【C语言】函数和递归
|
1天前
|
编译器 C语言 C++
c语言常见字符函数、内存函数(详讲)
c语言常见字符函数、内存函数(详讲)
|
1天前
|
存储 编译器 C语言
C语言程序设计——字符输入函数getchar()
C语言程序设计——字符输入函数getchar()
|
1天前
|
存储 编译器 C语言
C语言程序设计——字符输出函数putchar()
C语言程序设计——字符输出函数putchar()
|
1天前
|
存储 安全 C语言
C语言程序设计——格式输入函数scanf()
C语言程序设计——格式输入函数scanf()
|
2天前
|
算法 程序员 编译器
C语言初阶③(函数)知识点+编程作业(递归模拟strlen,pow)
C语言初阶③(函数)知识点+编程作业(递归模拟strlen,pow)
11 0
|
6天前
|
C语言
C语言—内存函数的实现和模拟实现(内存函数的丝绸之路)
C语言—内存函数的实现和模拟实现(内存函数的丝绸之路)
19 0