解题思路:
快速排序法是使用分治法的策略把一个串行分成两个子串行(即把数组以一个数为基准分为小于基准值的数列和大于基准值的数列)。快速排序法应该算是在冒泡排序法基础上的递归分治法。分为以下三个步骤:
1、取基准点
确定一个基准点,可以随机取。但是取数组中间的元素作为基准点,可以更快。
2、划分区间
把小于基准点的数无序放在基准点左边,大于基准点的数无序放在基准点右边。(代码实现原理:使用两个指针i和j,从数组左右两边开始走,如果不满足条件就互换)
3、递归排序
递归排序左右两边的数列,使之整个数组排好序。
注意事项:
一定要理解快速排序法的逻辑是什么,不然还是不懂。
1、基准点尽量去数组中间的元素,可以减少时间。
2、划分区间时,指针i不能是数组首元素下标,j不能说数组尾元素下标。因为do while循环,是先把i和j指针往前推一位再进行判断。要不然会把首尾元素没有排序。
3、递归排序左右两边时,要注意传入的参数
觉得写的不错的,麻烦各位点个评分或者评论,支持一下阿辉。谢谢
参考代码:
#include <stdio.h> void quick_sort(int nums[],int l,int r) { if(l >= r)//如果数组只有1个元素或者没有元素,直接退出函数 return; int i = l - 1,j = r + 1,x = nums[(l + r ) / 2];//i和j是指针,为了下面的do while循环,使用把它们往前后者往后推了一位,x为基准点 while(i < j)//开始划分区间,当i和j没有相遇时,继续走 { do i++;while(nums[i] < x); do j--;while(nums[j] > x); if(i < j)//如果i和j跳出do while循环,说明nums[i]比x大,nums[j]比x小,这两个数需要进行互换 { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } quick_sort(nums,l,j);//递归排序左边 quick_sort(nums,j + 1,r);//递归排序右边 } int main() { int n,nums[100000]; scanf("%d",&n); for(int i = 0;i < n;i++) { scanf("%d",&nums[i]); } quick_sort(nums,0,n - 1);//快速排序法 for(int i = 0;i < n;i++) { printf("%d ",nums[i]); } return 0; }
附yxc大佬的快排模板
void quick_sort(int nums[],int l,int r) { if(l >= r) return; int i = l - 1,j = r + 1,x = nums[(l + r) / 2]; while(i < j) { do i++;while(nums[i] < x); do j--;while(nums[j] > x); if(i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } quick_sort(nums,l,j); quick_sort(nums,j + 1,r); }
0.0分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复