对快速排序思想的进一步理解，分而治之，欧几里得算法（常用求最大公约数的方法）

发布时间：2024年01月13日

自己找到的最优的快排的代码

快速排序
思想
分而治之在这里插入图片描述使用欧几里得算法（辗转相除法）来求解一个应用题
假设有一块地，现在用这个同样大小的正方形来铺满，求所可用的最大的正方形地砖的面积
在这里插入图片描述在这里插入图片描述
这两个方法放在一起是因为这个欧几里得要使用递归
快排的思想，每次给这个序列的一个元素找到其正确的位置，且这个元素的左右两边的元素区间内有序，即这个元素的左边的所有元素都小于等于这个元素，右边的所有元素都大于等于这个元素。
在这里插入图片描述如图，给这个第一个元素进行排列，第一趟，就给第一个元素找到了其正确的位置，
而下一趟就是利用递归同时对8 的左边和右边进行快排。
快速排序的性能高度依赖所选的基准值
在这里插入图片描述其实得根据算法每次选的枢轴，如果是随机选，就可以避免第一种有序时的最坏情况，如果不是随机选，而是每次都选每个分区的第一个元素，就会
使时间复杂度变成最坏的情况O(n^2)

文章来源:https://blog.csdn.net/weixin_45800887/article/details/135574734
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章