1、 qsort 函數

1.1、qsort 函數排列結構體

在這里，我們創建結構體類型的數組，用于 qsort 函數的傳參。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>struct Stu//創建結構體變量
{char name[30];int age;
};struct Stu arr[] = { { "zhangsan", 18 }, { "lisi", 20 }, { "wangwu", 38 } };void Print(struct Stu* p, int sz)//打印函數
{for (int i = 0; i < sz; i++){printf("%s: %d\n", p->name, p->age);p++;}
}cmp_str_by_age(const void* p1, const void* p2)//排年齡函數
{return (((struct Stu*)p1)->age - ((struct Stu*)p2)->age);
}test1()//按年齡大小
{int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_str_by_age);Print(arr, sz);
}cmp_str_by_name(const void* p1, const void* p2)//排姓名函數
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}test2()//按姓名
{int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_str_by_name);Print(arr, sz);
}int main()
{test1();printf("-------------------------\n");test2();return 0;
}

這里講兩點：

1、結構成員訪問操作符: ->

使用方法為：結構體指針 -> 成員變量。上面代碼中，?((struct Stu*)p1)->age 也可以換為?*(struct Stu*)p1.age 。

2、 strcmp 函數

使用方法為，向函數中傳入兩個字符串類型的數據，比較對應位置字符的 ASCII 碼值的大小。以順序為例，若前一個字符串對應位置字符的 ASCII 碼值應大于后一個，返回大于0的值；相等返回0，小于返回小于0的值。

1.2、 qsort 函數的模擬實現

既然要實現 qsort 函數，那么向其中傳入的參數，也應該是：首元素地址、元素個數、元素大小、比較函數。

#include<stdio.h>int int_cmp(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void Bubble_qsort(void* base, int count, int size, int (*cmp)(void*, void*))}void test1()
{int arr[] = { 4,5,2,7,9,12,34,101 };int count = sizeof(arr) / sizeof(arr[0]);Bubble_qsort(arr, count, sizeof(arr[0]), int_cmp);
}int main()
{test1();//實現整型值的排序return 0;
}

將這個函數的名字取為?Bubble_qsort ，是因為我們將用冒泡排列的方式來模擬實現 qsort 函數。

所以，我們要交代趟數，也要交代每趟交換數據的次數。

而交換操作中，我們可以將每兩個數（的地址）傳入 int_cmp 函數中，觀察返回的值。若返回正數值，則再創建一個交換函數。

但是， void* 類型的指針不能進行任何操作。也許會用強制類型轉換，轉換成什么？ int* ？但這可是在模擬 qsort 函數，這個函數原來是可以排列任意類型的數據的。

所以，我們不妨將 void* 類型，強制轉換成 char* 類型 。

#include<stdio.h>int int_cmp(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void Swap(char* buf1, char* buf2)
{}void Bubble_qsort(void* base, int count, int size, int (*cmp)(void*, void*))
{for (int i = 0; i < count - 1; i++){for (int j = 0; j < count - i - 1; j++){if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0){Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}void test1()
{int arr[] = { 4,5,2,7,9,12,34,101 };int count = sizeof(arr) / sizeof(arr[0]);Bubble_qsort(arr, count, sizeof(arr[0]), int_cmp);
}int main()
{test1();//實現整型值的排序return 0;
}

而在交換函數中，既然地址已被強制轉換成 char* ，那么我們就不能一次性交換干凈，而是一點一點交換。交換的次數，自然是元素的大小。

#include<stdio.h>void Print(int arr[], int count)//打印函數
{for (int i = 0; i < count; i++){printf("%d ", arr[i]);}printf("\n");
}int int_cmp(const void* p1, const void* p2)//比較函數
{return *(int*)p1 - *(int*)p2;
}void Swap(char* buf1, char* buf2, int size)//交換函數
{for (int i = 0; i < size; i++){char tmp = *(buf1 + i);*(buf1 + i) = *(buf2 + i);*(buf2 + i) = tmp;}
}void Bubble_qsort(void* base, int count, int size, int (*cmp)(void*, void*))
{                                                   //模擬 qsort 的函數for (int i = 0; i < count - 1; i++){for (int j = 0; j < count - i - 1; j++){if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0){Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}void test1()
{int arr[] = { 4,5,2,7,9,12,34,101 };int count = sizeof(arr) / sizeof(arr[0]);Print(arr, count);Bubble_qsort(arr, count, sizeof(arr[0]), int_cmp);Print(arr, count);
}int main()
{test1();//實現整型值的排序return 0;
}

這樣一來，這個函數連結構體都能排列。但是要加一點比較函數代碼：

#include<stdio.h>struct Stu//創建結構體
{char name[30];int age;
};void Print(int arr[], int count)//打印函數
{for (int i = 0; i < count; i++){printf("%d ", arr[i]);}printf("\n");
}void Print1(struct Stu* p, int sz)//打印結構體
{for (int i = 0; i < sz; i++){printf("%s: %d\n", p->name, p->age);p++;}
}int int_cmp(const void* p1, const void* p2)//比較函數
{return *(int*)p1 - *(int*)p2;
}int cmp_str_by_name(const void* p1, const void* p2)//比較字符串
{if (strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name) > 0)return 1;else if (strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name) < 0)return -1;elsereturn 0;
}void Swap(char* buf1, char* buf2, int size)//交換函數
{for (int i = 0; i < size; i++){char tmp = *(buf1 + i);*(buf1 + i) = *(buf2 + i);*(buf2 + i) = tmp;}
}void Bubble_qsort(void* base, int count, int size, int (*cmp)(void*, void*))
{                                                   //模擬 qsort 的函數for (int i = 0; i < count - 1; i++){for (int j = 0; j < count - i - 1; j++){if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0){Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}void test1()
{int arr[] = { 4,5,2,7,9,12,34,101 };int count = sizeof(arr) / sizeof(arr[0]);Print(arr, count);Bubble_qsort(arr, count, sizeof(arr[0]), int_cmp);Print(arr, count);
}void test2()
{struct Stu arr[] = { { "zhangsan", 18 }, { "lisi", 20 }, { "wangwu", 38 } };int count = sizeof(arr) / sizeof(arr[0]);Print1(arr, count);printf("-------------------------\n");Bubble_qsort(arr, count, sizeof(arr[0]), cmp_str_by_name);Print1(arr, count);
}int main()
{//test1();//實現整型值的排序test2();//實現結構體的排列return 0;
}