资溪县建设局网站,黄金网站app视频,公司优化是什么意思,网站开发相关外文书籍快速排序#xff08;Quick Sort#xff09;是计算机科学与技术领域中非常经典的一种排序算法#xff0c;由C. A. R. Hoare在1960年提出。它应用分治思想进行排序#xff0c;通过对数据进行分区操作#xff0c;并递归地对分区后的子序列进行排序#xff0c;从而达到整个序…快速排序Quick Sort是计算机科学与技术领域中非常经典的一种排序算法由C. A. R. Hoare在1960年提出。它应用分治思想进行排序通过对数据进行分区操作并递归地对分区后的子序列进行排序从而达到整个序列有序的目的。
基本思想
快速排序的核心思想是在待排序序列中选择一个基准值pivot然后将小于基准值的元素放在基准值的左边大于基准值的元素放在基准值的右边这样就找到了基准值在数组中的正确位置。之后再分别对基准值左右两边的子序列进行同样的操作直到整个序列有序。
排序流程
快速排序算法通过多次比较和交换来实现排序其排序流程大致如下
选择基准值在待排序序列中选取一个元素作为基准值。分区操作通过一趟排序将待排序的数据分割成独立的两部分其中一部分的所有数据都比另一部分的所有数据要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。递归排序对基准值左右两边的子序列递归地执行上述分区操作直到子序列的长度为1或0即已经有序。
排序步骤
以数组为例快速排序的详细步骤可以归纳为
设置两个指针通常设置两个指针i和j分别指向序列的起始位置和末尾位置。选择基准值可以选择序列的第一个元素作为基准值也可以采用其他策略选择基准值。分区操作 从后往前搜索j--找到第一个小于基准值的元素A[j]将其与A[i]交换。从前往后搜索i找到第一个大于基准值的元素A[i]将其与A[j]交换。重复上述步骤直到i和j相遇此时基准值就位于其最终位置。递归排序对基准值左边的子序列和右边的子序列分别进行快速排序。
性能分析
时间复杂度快速排序的平均时间复杂度为O(n log n)但在最坏情况下如输入序列已经有序或接近有序时间复杂度会退化到O(n^2)。这通常是由于基准值选择不当导致的。空间复杂度快速排序的空间复杂度主要取决于递归的深度。在最好的情况下递归深度为logn空间复杂度为O(logn)。但在最坏情况下递归深度可能达到n空间复杂度为O(n)。然而由于快速排序是原地排序in-place sort除了递归所需的栈空间外不需要额外的存储空间因此可以认为其空间复杂度是O(logn)不考虑递归栈。
注意事项
快速排序不是一种稳定的排序算法即相同的元素在排序后可能会改变它们之间的相对位置。快速排序的性能受到基准值选择策略的影响因此在实际应用中需要选择合适的基准值选择策略以提高排序效率。
随机值
在快速排序中选择基准值pivot的策略对算法的性能有着显著的影响。传统的快速排序实现可能会选择序列的第一个、最后一个或中间元素作为基准值但这些策略在某些情况下如输入序列已经部分或完全有序可能导致算法性能退化到O(n^2)。
为了避免这种情况一种常用的改进方法是随机选择基准值。通过随机选择基准值可以大大减少算法陷入最坏情况的可能性从而提高算法的平均性能。
随机选择基准值的步骤 生成随机数首先生成一个随机数randIdx该随机数的范围是0到n-1其中n是序列的长度。 选择基准值然后将randIdx对应的元素选为基准值。这通常涉及到将基准值元素与序列的某个位置如第一个或最后一个位置的元素进行交换以便于后续的分区操作。 进行分区使用选定的基准值对序列进行分区操作将小于基准值的元素放在基准值的左边大于基准值的元素放在基准值的右边。 递归排序对基准值左边和右边的子序列递归地执行上述过程直到子序列的长度为0或1。
优点 减少最坏情况的发生随机选择基准值可以显著降低算法陷入最坏情况即每次分区都只得到一个空子序列的可能性。 提高平均性能通过随机化算法的平均性能更加稳定不易受到输入数据的影响。
注意事项 随机数的生成在生成随机数时需要确保随机数生成器的质量以避免产生可预测的序列。 实现复杂度虽然随机选择基准值可以提高性能但它也增加了实现的复杂度。特别是在多线程或并行快速排序的实现中需要更加小心地处理随机数的生成和基准值的选择。 内存和性能权衡在某些情况下为了生成随机数和进行交换操作可能会引入额外的内存访问和计算开销。然而这些开销通常远小于因避免最坏情况而获得的性能提升。
912. 排序数组
给你一个整数数组 nums请你将该数组升序排列。
示例 1
输入nums [5,2,3,1]
输出[1,2,3,5]示例2
输入nums [5,1,1,2,0,0]
输出[0,0,1,1,2,5]提示
1 nums.length 5 * 104-5 * 104 nums[i] 5 * 104
若令第一个值为基准元素提交会显示不通过超时
class Solution {
public:void quicksort( vectorint nums ,int i,int j){if(ij){ int li,rj;int pltnums[l];while(lr){while (l r nums[r] plt) r--;while (l r nums[l] plt) l;if(lr){swap(nums[l],nums[r]);}}swap(nums[l],nums[i]);quicksort(nums,i,r-1);quicksort(nums,l1,j);}}vectorint sortArray(vectorint nums) {int i0;int jnums.size()-1;quicksort(nums,i,j);return nums;}
};基准值采用随机值可以通过 class Solution {
public:void quicksort( vectorint nums ,int i,int j){if(ij){ int li,rj;int x rand() % (r - l 1) l; // 基于随机的原则swap(nums[l], nums[x]);int pltnums[l];while(lr){while (l r nums[r] plt) r--;while (l r nums[l] plt) l;if(lr){swap(nums[l],nums[r]);}}swap(nums[l],nums[i]);quicksort(nums,i,r-1);quicksort(nums,l1,j);}}vectorint sortArray(vectorint nums) {int i0;int jnums.size()-1;quicksort(nums,i,j);return nums;}
};
