有关排序的算法
排序是我们日常生活中比较常见的问题，这里我们来说叨几个排序的算法。
比如有一个一维数组 arr[8] ={2,5,3,1,7,6,4,8},我们想要把它排成升序，我们通过下面这几种不同的方式来进行排序！
选择法排序
这一种排序方式，首先第一轮认为第一个元素是最小的，把它的下标用 flag 记下来，不断与后面的元素进行比较，如果后面的元素有比它小的，就把 flag 改成比它小的元素下标，直到把整个数组下标遍历完，如果flag不等于最开始的下标就进行交换，这样就可以得到最小的那个数在第一位，依此类推，第二轮找到第二小的数字放在第二位，第三轮找到第三小的数字放在第三位……
当第七轮的时候已经找到了找到第七小的数字放在第七位，显然最后一位是最大的数字，所以一共进行七次就好了！
代码如下：
//选择法排序
#include<stdio.h>
int main()
{
int arr[8] = { 2,5,3,1,7,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int j = 0;
int flag = 0;
printf("排序前：\n");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
for (i = 0; i < sz - 1; i++)
{
flag = i;
for (j = i + 1; j < sz; j++)
{
if (arr[j] < arr[flag])
flag = j;
//如果后面的元素比flag为坐标的元素小，就把flag改成较小元素的坐标
}
if (flag != i)
{
int temp = arr[i];
arr[i] = arr[flag];
arr[flag] = temp
}
}
printf("\n排序后：\n");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}当然，在学习了指针的基础上，我们可以把排序代码分装成函数的形式
#include<stdio.h>
void Print_arr(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
printf("%d ", arr[i]);
}
void Choose_sort(int* arr, int sz)
{
int flag = 0;
for (int i = 0; i < sz - 1; i++)
{
flag = i;
for (int j = i + 1; j < sz; j++)
{
if (arr[j] < arr[flag])
flag = j;
}
if (flag != i)
{
int temp = arr[i];
arr[i] = arr[flag];
arr[flag] = temp;
}
}
}
int main()
{
int arr[8] = { 2,5,3,1,7,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
Choose_sort(arr, sz);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}
冒泡法排序
这个与选择法排序有点相似，它的核⼼思想是两两相邻的元素进⾏⽐较，如果后面的元素比前面小，那么就立刻进行交换，第一轮最终会把最大的元素放在最后一位，依次往后面推进，在第七轮的时候，第二小的就在第二位了，所以只需要7趟就好了，每一趟就会找到一个元素放在相应的位置，所以每一趟比较的数组元素也会依次减1.
代码如下：
//冒泡排序
#include<stdio.h>
int main()
{
int arr[8] = { 2,5,3,1,7,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int j = 0;
printf("排序前：\n");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
for (i = 0; i < sz - 1; i++)
{
//i代表趟数
for (j = 0 ; j < sz - 1 - i; j++)
{
//访问数组元素两两比较
if ( arr[j+1]<arr[j])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printf("\n排序后：\n");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
我们也可以把排序代码分装成函数的形式：
#include<stdio.h>
void Print_arr(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;
int j = 0;
for (i = 0; i < sz - 1; i++)
{
for (j = 0; j < sz - 1 - i; j++)
{
if (*(arr+j+1) < *(arr+j))
{
int temp = *(arr + j + 1);
*(arr + j + 1) = *(arr + j);
*(arr + j) = temp;
}
/*if (arr[j + 1] < arr[j])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}*/
}
}
}
int main()
{
int arr[8] = { 2,5,3,1,7,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
Bubble_sort(arr, sz);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}
我们来考虑一个问题，如果一个数组元素已经有序了，事实上，我们可以不用再进行排序了，那么应该怎么优化这个排序代码呢？
#include<stdio.h>
void Print_arr(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;
int j = 0;
for (i = 0; i < sz - 1; i++)
{
int flag = 1;//最开始就假设有序
for (j = 0; j < sz - 1 - i; j++)
{
if (*(arr + j + 1) < *(arr + j))
{
flag = 0;//进来就说明还没有有序，让flag=0
int temp = *(arr + j + 1);
*(arr + j + 1) = *(arr + j);
*(arr + j) = temp;
}
}
if (flag == 1)//一趟下来flag=1，说明没有机会让flag=0，已经有序
{
printf("\n已经有序！\n");
break;
}
}
}
int main()
{
int arr[8] = { 1,2,3,4,5,6,7,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
Bubble_sort(arr, sz);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}
这里我们就可以使用一个flag来进行标记，flag=1，就说明已经有序，跳出循环，当一个数组已经已经有序或者接近有序的时候就可以减少运算次数！
qsort排序（快速排序）
想要使用qsort函数呢？我们就需要先对这个函数进行一定的了解。
打开cplusplus网站，我们可以找到相关信息：
qsort（quick sort）事实上是C语言中的一个库函数，底层使用的是快速排序的思想，
并且对任意类型数据都可以进行排序。
我们来看看每一个参数
base：指向需要排序数组的首元素地址（指针） num:base指向数组中的元素个数 size：bas指向的数组中一个元素的字节大小 compar:函数指针，传递函数的地址
compar应该设计成下面这个样子，同时它的返回值也有要求
int compar (const void* p1, const void* p2); 当p1指向的元素小于p2指向的元素时，返回一个小于0的数字 当p1指向的元素等于p2指向的元素时，返回0 当p1指向的元素大于p2指向的元素时，返回一个大于0的数字 |
|---|
qsort排序整型
//测试qsort排序整型
#include<stdio.h>
#include<stdlib.h>
void Print_arr(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
printf("%d ", arr[i]);
}
int cmp_int(const void* p1, const void* p2)
{
if (*(int*)p1 > *(int*)p2)
{
return 1;
}
//知道比较整型，强制类型转换为整型，然后解引用
else if (*(int*)p1 < *(int*)p2)
{
return -1;
}
else
{
return 0;
}
}
int main()
{
int arr[8] = { 2,5,3,1,7,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}
我们可以看见qsort进行了很好的排序，当然这里因为它的规则是
当p1指向的元素小于p2指向的元素时，返回一个小于0的数字
当p1指向的元素等于p2指向的元素时，返回0
当p1指向的元素大于p2指向的元素时，返回一个大于0的数字
所以我们可以把return语句直接写成：
return *((int*)p1) - *((int*)p2);
#include<stdio.h>
#include<stdlib.h>
void Print_arr(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
printf("%d ", arr[i]);
}
int cmp_int(const void* p1, const void* p2)
{
//return *((int*)p1) - *((int*)p2);//默认升序
//知道比较整型，强制类型转换为整型，然后解引用
return *((int*)p2) - *((int*)p1); // 降序
}
int main()
{
int arr[8] = { 2,5,3,1,7,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}使用qsort默认是升序，如果想要降序，交换p1，p2的位置就可以了，比如上面的代码就可以实现降序。
qsort排序结构体类型
//qsort排序结构体类型
#include<stdio.h>
#include<stdlib.h>//qsort头文件
#include<string.h>//strcmp头文件
struct Student
{
char name[20];
int age;
};
void Print_arr(struct Student* arr, int sz)
{
for (int i = 0; i < sz; i++)
printf("%s %d\n", arr[i].name, arr[i].age);
}
int cmp_student_by_name(const void* p1, const void* p2)
{
return strcmp(((struct Student*)p1)->name, ((struct Student*)p2)->name);
//strcmp比较字符串，比较第一个不同字符的ASCII值
}
int main()
{
struct Student arr[3] = { {"lihua",18},{"balla",56},{"guna",23} };
//结构体数组
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
qsort(arr, sz, sizeof(arr[0]), cmp_student_by_name);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}这里依然是比较的时候强制类型转换为结构体类型，使用了结构体访问操作符【->】特殊的是比较字符串需要使用strcmp函数，不清楚的可以看看【数组的使用】那一篇博客对strcmp进行详细讲解。
我们也可以通过年龄来比较，代码如下：
#include<stdio.h>
#include<stdlib.h>//qsort头文件
//#include<string.h>//strcmp头文件
struct Student
{
char name[20];
int age;
};
void Print_arr(struct Student* arr, int sz)
{
for (int i = 0; i < sz; i++)
printf("%s %d\n", arr[i].name, arr[i].age);
}
int cmp_student_by_age(const void* p1, const void* p2)
{
return (((struct Student*)p1)->age - ((struct Student*)p2)->age);
}
int main()
{
struct Student arr[3] = { {"lihua",18},{"balla",56},{"guna",23} };
//结构体数组
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
Print_arr(arr, sz);
qsort(arr, sz, sizeof(arr[0]), cmp_student_by_age);
printf("\n排序后：\n");
Print_arr(arr, sz);
return 0;
}
当然排序算法永远不止于此，还有更多的内容等待着我们去发现，去应用。
加油吧！未来的顶尖程序员们！！！！
腾讯云开发者
