目录
选择法排序
冒泡法排序
qsort排序(快速排序)
qsort排序整型
qsort排序结构体类型
排序是我们日常生活中比较常见的问题,这里我们来说叨几个排序的算法。
比如有一个一维数组 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=0int 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应该设计成下面这个样子,同时它的返回值也有要求
|
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;
}
当然排序算法永远不止于此,还有更多的内容等待着我们去发现,去应用。
加油吧!未来的顶尖程序员们!!!!