• 有关排序的算法

    目录

    选择法排序

    冒泡法排序

    qsort排序（快速排序）

    qsort排序整型

    qsort排序结构体类型

    排序是我们日常生活中比较常见的问题，这里我们来说叨几个排序的算法。

    比如有一个一维数组 arr[8] ={2,5,3,1,7,6,4,8},我们想要把它排成升序，我们通过下面这几种不同的方式来进行排序！

    选择法排序

    这一种排序方式，首先第一轮认为第一个元素是最小的，把它的下标用 flag 记下来，不断与后面的元素进行比较，如果后面的元素有比它小的，就把 flag 改成比它小的元素下标，直到把整个数组下标遍历完，如果flag不等于最开始的下标就进行交换，这样就可以得到最小的那个数在第一位，依此类推，第二轮找到第二小的数字放在第二位，第三轮找到第三小的数字放在第三位……

    当第七轮的时候已经找到了找到第七小的数字放在第七位，显然最后一位是最大的数字，所以一共进行七次就好了！

    代码如下：

    1. //选择法排序
    2. #include
    3. int main()
    4. {
    5. 	int arr[8] = { 2,5,3,1,7,6,4,8 };
    6. 	int sz = sizeof(arr) / sizeof(arr[0]);
    7. 	int i = 0;
    8. 	int j = 0;
    9. 	int flag = 0;
    10. 	printf("排序前：\n");
    11. 	for (i = 0; i < sz; i++)
    12. 	{
    13. 		printf("%d ", arr[i]);
    14. 	}
    15. 	for (i = 0; i < sz - 1; i++)
    16. 	{
    17. 		flag = i;
    18. 		for (j = i + 1; j < sz; j++)
    19. 		{
    20. 			if (arr[j] < arr[flag])
    21. 				flag = j;
    22. 			//如果后面的元素比flag为坐标的元素小，就把flag改成较小元素的坐标
    23. 		}
    24. 		if (flag != i)
    25. 		{
    26. 			int temp = arr[i];
    27. 			arr[i] = arr[flag];
    28. 			arr[flag] = temp
    29. 		}
    30. 	}
    31. 	printf("\n排序后：\n");
    32. 	for (i = 0; i < sz; i++)
    33. 	{
    34. 		printf("%d ", arr[i]);
    35. 	}
    36. 	return 0;
    37. }
    38.  
    39.

    当然，在学习了指针的基础上，我们可以把排序代码分装成函数的形式

    1.  
    2. #include
    3. void Print_arr(int* arr, int sz)
    4. {
    5. 	for (int i = 0; i < sz; i++)
    6. 		printf("%d ", arr[i]);
    7. }
    8. void Choose_sort(int* arr, int sz)
    9. {
    10. 	int flag = 0;
    11. 	for (int i = 0; i < sz - 1; i++)
    12. 	{
    13. 		flag = i;
    14. 		for (int j = i + 1; j < sz; j++)
    15. 		{
    16. 			if (arr[j] < arr[flag])
    17. 				flag = j;
    18. 		}
    19. 		if (flag != i)
    20. 		{
    21. 			int temp = arr[i];
    22. 			arr[i] = arr[flag];
    23. 			arr[flag] = temp;
    24. 		}
    25. 	}
    26. }
    27. int main()
    28. {
    29. 	int arr[8] = { 2,5,3,1,7,6,4,8 };
    30. 	int sz = sizeof(arr) / sizeof(arr[0]);
    31. 	printf("排序前：\n");
    32. 	Print_arr(arr, sz);
    33. 	Choose_sort(arr, sz);
    34. 	printf("\n排序后：\n");
    35. 	Print_arr(arr, sz);
    36. 	return 0;
    37. }
    38.  
    39.  
    40.

    冒泡法排序

    这个与选择法排序有点相似，它的核⼼思想是两两相邻的元素进⾏⽐较，如果后面的元素比前面小，那么就立刻进行交换，第一轮最终会把最大的元素放在最后一位，依次往后面推进，在第七轮的时候，第二小的就在第二位了，所以只需要7趟就好了，每一趟就会找到一个元素放在相应的位置，所以每一趟比较的数组元素也会依次减1.

    代码如下：

    1.  
    2. //冒泡排序
    3. #include
    4. int main()
    5. {
    6. 	int arr[8] = { 2,5,3,1,7,6,4,8 };
    7. 	int sz = sizeof(arr) / sizeof(arr[0]);
    8. 	int i = 0;
    9. 	int j = 0;
    10. 	printf("排序前：\n");
    11. 	for (i = 0; i < sz; i++)
    12. 	{
    13. 		printf("%d ", arr[i]);
    14. 	}
    15. 	for (i = 0; i < sz - 1; i++)
    16. 	{
    17. 		//i代表趟数
    18. 		for (j = 0 ; j < sz - 1 - i; j++)
    19. 		{
    20. 			//访问数组元素两两比较
    21. 			if ( arr[j+1]
    22. 			{
    23. 				int temp = arr[j];
    24. 				arr[j] = arr[j+1];
    25. 				arr[j+1] = temp;
    26. 			}		
    27. 		}	
    28. 	}
    29. 	printf("\n排序后：\n");
    30. 	for (i = 0; i < sz; i++)
    31. 	{
    32. 		printf("%d ", arr[i]);
    33. 	}
    34. 	return 0;
    35. }

    我们也可以把排序代码分装成函数的形式：

    1. #include
    2. void Print_arr(int* arr, int sz)
    3. {
    4. 	for (int i = 0; i < sz; i++)
    5. 		printf("%d ", arr[i]);
    6. }
    7. void Bubble_sort(int* arr, int sz)
    8. {
    9. 	int i = 0;
    10. 	int j = 0;
    11. 	for (i = 0; i < sz - 1; i++)
    12. 	{
    13. 		for (j = 0; j < sz - 1 - i; j++)
    14. 		{
    15. 			if (*(arr+j+1) < *(arr+j))
    16. 			{
    17. 				int temp = *(arr + j + 1);
    18. 				*(arr + j + 1) = *(arr + j);
    19. 				*(arr + j) = temp;
    20. 			}
    21. 			/*if (arr[j + 1] < arr[j])
    22. 			{
    23. 				int temp = arr[j];
    24. 				arr[j] = arr[j + 1];
    25. 				arr[j + 1] = temp;
    26. 			}*/
    27. 		}
    28. 	}
    29. }
    30. int main()
    31. {
    32. 	int arr[8] = { 2,5,3,1,7,6,4,8 };
    33. 	int sz = sizeof(arr) / sizeof(arr[0]);
    34. 	printf("排序前：\n");
    35. 	Print_arr(arr, sz);
    36. 	Bubble_sort(arr, sz);
    37. 	printf("\n排序后：\n");
    38. 	Print_arr(arr, sz);
    39. 	return 0;
    40. }
    41.  
    42.  
    43.

    我们来考虑一个问题，如果一个数组元素已经有序了，事实上，我们可以不用再进行排序了，那么应该怎么优化这个排序代码呢？

    1. #include
    2. void Print_arr(int* arr, int sz)
    3. {
    4. 	for (int i = 0; i < sz; i++)
    5. 		printf("%d ", arr[i]);
    6. }
    7. void Bubble_sort(int* arr, int sz)
    8. {
    9. 	int i = 0;
    10. 	int j = 0;
    11. 	for (i = 0; i < sz - 1; i++)
    12. 	{
    13. 		int flag = 1;//最开始就假设有序
    14. 		for (j = 0; j < sz - 1 - i; j++)
    15. 		{
    16. 			if (*(arr + j + 1) < *(arr + j))
    17. 			{
    18. 				flag = 0;//进来就说明还没有有序，让flag=0
    19. 				int temp = *(arr + j + 1);
    20. 				*(arr + j + 1) = *(arr + j);
    21. 				*(arr + j) = temp;
    22. 			}
    23. 		}
    24. 		if (flag == 1)//一趟下来flag=1，说明没有机会让flag=0，已经有序
    25. 		{
    26. 			printf("\n已经有序！\n");
    27. 			break;
    28. 		}
    29. 	}
    30. }
    31. int main()
    32. {
    33. 	int arr[8] = { 1,2,3,4,5,6,7,8 };
    34. 	int sz = sizeof(arr) / sizeof(arr[0]);
    35. 	printf("排序前：\n");
    36. 	Print_arr(arr, sz);
    37. 	Bubble_sort(arr, sz);
    38. 	printf("\n排序后：\n");
    39. 	Print_arr(arr, sz);
    40. 	return 0;
    41. }
    42.  
    43.  
    44.

    这里我们就可以使用一个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排序整型
     

    1. //测试qsort排序整型
    2.  
    3. #include
    4. #include
    5. void Print_arr(int* arr, int sz)
    6. {
    7. 	for (int i = 0; i < sz; i++)
    8. 		printf("%d ", arr[i]);
    9. }
    10. int cmp_int(const void* p1, const void* p2)
    11. {
    12. 	if (*(int*)p1 > *(int*)p2)
    13. 	{
    14. 		return 1;
    15. 	}
    16. 	//知道比较整型，强制类型转换为整型，然后解引用
    17. 	else if (*(int*)p1 < *(int*)p2)
    18. 	{
    19. 		return -1;
    20. 	}
    21. 	else
    22. 	{
    23. 		return 0;
    24. 	}
    25. }
    26. int main()
    27. {
    28. 	int arr[8] = { 2,5,3,1,7,6,4,8 };
    29. 	int sz = sizeof(arr) / sizeof(arr[0]);
    30. 	printf("排序前：\n");
    31. 	Print_arr(arr, sz);
    32. 	qsort(arr, sz, sizeof(arr[0]), cmp_int);
    33. 	printf("\n排序后：\n");
    34. 	Print_arr(arr, sz);
    35. 	return 0;
    36. }
     

     

    我们可以看见qsort进行了很好的排序，当然这里因为它的规则是
     

    当p1指向的元素小于p2指向的元素时，返回一个小于0的数字
     

    当p1指向的元素等于p2指向的元素时，返回0
     

    当p1指向的元素大于p2指向的元素时，返回一个大于0的数字
     

    所以我们可以把return语句直接写成：
     

     
 
    return *((int*)p1) - *((int*)p2);
     

     

    1. #include
    2. #include
    3. void Print_arr(int* arr, int sz)
    4. {
    5. 	for (int i = 0; i < sz; i++)
    6. 		printf("%d ", arr[i]);
    7. }
    8. int cmp_int(const void* p1, const void* p2)
    9. {
    10. 	//return *((int*)p1) - *((int*)p2);//默认升序
    11. 	//知道比较整型，强制类型转换为整型，然后解引用
    12. 	return *((int*)p2) - *((int*)p1); // 降序
    13. }
    14. int main()
    15. {
    16. 	int arr[8] = { 2,5,3,1,7,6,4,8 };
    17. 	int sz = sizeof(arr) / sizeof(arr[0]);
    18. 	printf("排序前：\n");
    19. 	Print_arr(arr, sz);
    20. 	qsort(arr, sz, sizeof(arr[0]), cmp_int);
    21. 	printf("\n排序后：\n");
    22. 	Print_arr(arr, sz);
    23. 	return 0;
    24. }
    25.  
    26.  
     

    使用qsort默认是升序，如果想要降序，交换p1，p2的位置就可以了，比如上面的代码就可以实现降序。
     

     

    qsort排序结构体类型
     

     

    1. //qsort排序结构体类型
    2. #include
    3. #include//qsort头文件
    4. #include//strcmp头文件
    5. struct Student
    6. {
    7. 	char name[20];
    8. 	int age;
    9. };
    10. void Print_arr(struct Student* arr, int sz)
    11. {
    12. 	for (int i = 0; i < sz; i++)
    13. 		printf("%s %d\n", arr[i].name, arr[i].age);
    14. }
    15. int cmp_student_by_name(const void* p1, const void* p2)
    16. {
    17. 	return strcmp(((struct Student*)p1)->name, ((struct Student*)p2)->name);
    18. 	//strcmp比较字符串，比较第一个不同字符的ASCII值
    19. }
    20. int main()
    21. {
    22. 	struct Student arr[3] = { {"lihua",18},{"balla",56},{"guna",23} };
    23. 	//结构体数组
    24. 	int sz = sizeof(arr) / sizeof(arr[0]);
    25. 	printf("排序前：\n");
    26. 	Print_arr(arr, sz);
    27. 	qsort(arr, sz, sizeof(arr[0]), cmp_student_by_name);
    28. 	printf("\n排序后：\n");
    29. 	Print_arr(arr, sz);
    30. 	return 0;
    31. }
     

    这里依然是比较的时候强制类型转换为结构体类型，使用了结构体访问操作符【->】特殊的是比较字符串需要使用strcmp函数，不清楚的可以看看【数组的使用】那一篇博客对strcmp进行详细讲解。
     

     

    我们也可以通过年龄来比较，代码如下：
     

    1. #include
    2. #include//qsort头文件
    3. //#include//strcmp头文件
    4. struct Student
    5. {
    6. 	char name[20];
    7. 	int age;
    8. };
    9. void Print_arr(struct Student* arr, int sz)
    10. {
    11. 	for (int i = 0; i < sz; i++)
    12. 		printf("%s %d\n", arr[i].name, arr[i].age);
    13. }
    14. int cmp_student_by_age(const void* p1, const void* p2)
    15. {
    16. 	return (((struct Student*)p1)->age - ((struct Student*)p2)->age);
    17. }
    18. int main()
    19. {
    20. 	struct Student arr[3] = { {"lihua",18},{"balla",56},{"guna",23} };
    21. 	//结构体数组
    22. 	int sz = sizeof(arr) / sizeof(arr[0]);
    23. 	printf("排序前：\n");
    24. 	Print_arr(arr, sz);
    25. 	qsort(arr, sz, sizeof(arr[0]), cmp_student_by_age);
    26. 	printf("\n排序后：\n");
    27. 	Print_arr(arr, sz);
    28. 	return 0;
    29. }
    30.  
    31.  
     

     

    当然排序算法永远不止于此，还有更多的内容等待着我们去发现，去应用。
     

    加油吧！未来的顶尖程序员们！！！！
    
                
    
                    
    
                
    • 

                
  • 

                    相关阅读:
    
                    
golang正则regexp包使用-05-扩展Expand()、根据正则切割Split()                            
    
用数据流量不能访问搭建好的网站                            
    
开启Windows11 PC无线热点功能                            
    
双周赛117（容斥原理、记忆化搜索==＞动态规划、分组背包方案数、脑经急转弯）                            
    
程序调试介绍及其使用                            
    
SSL单向认证原理                            
    
程序中的地址如何转换？                            
    
【技术积累】Linux中的命令行【理论篇】【六】                            
    
数仓SQL相关的场景解法                            
    
什么是 Infamous Skullz NFT 系列?                            
    
                        
                
    • 
                
  • 
                    原文地址：https://blog.csdn.net/2401_82924480/article/details/139645774
                
    •