扮家家室内设计网,南阳网站优化,金融软件外包公司,cn网站排序是算法的入门知识#xff0c;应用广泛#xff0c;且在程序员面试中#xff0c;经常被提及#xff0c;其中最常考的两大排序算法为快速排序与归并排序#xff0c;本篇将使用Python语言来分析了解快速排序算法。思想 快速排序是一种非常高效的排序算法#xff0c;采用 …排序是算法的入门知识应用广泛且在程序员面试中经常被提及其中最常考的两大排序算法为快速排序与归并排序本篇将使用Python语言来分析了解快速排序算法。 思想 快速排序是一种非常高效的排序算法采用 “分而治之” 的思想把大的拆分为小的小的拆分为更小的。其原理是对于给定的记录选择一个基准数通过一趟排序后将原序列分为两部分使得前面的比后面的小然后再依次对前后进行拆分进行快速排序递归该过程直到序列中所有记录均有序。步骤设当前待排序序列为R[low:high]其中low ≤ high如果待排序的序列规模足够小则直接进行排序否则分3步处理。1、分解在R[low:high]中选定一个元素R[pivot]以此为标准将要排序的序列划分为两个序列R[low:pivot-1]与R[pivot1high]并使序列R[low:pivot-1]中所有元素的值小于等于R[pivot]序列R[pivot1high]所有的值大于R[pivot]此时基准元素以位于正确位置它无需参加后续排序。2、递归对于子序列R[low:pivot-1]与R[pivot1high]分别调用快速排序算法来进行排序。3、合并由于对序列R[low:pivot-1]与R[pivot1high]的排序是原地进行的所以R[low:pivot-1]与R[pivot1high]都已经排好序后不需要进行任何计算就已经排好序。注基准元素一般来说选取有几种方法取第一个元素取最后一个元素取第中间位置元素取第一个、最后一个、中间位置3者的中位数元素图解假设当前排序为R[low:high]其中low ≤ high。1首先取序列第一个元素为基准元素pivotR[low]。ilow,jhigh。 2从后向前扫描找小于等于pivot的数如果找到R[i]与R[j]交换i。 3从前往后扫描找大于pivot的数如果找到R[i]与R[j]交换j--。 4:重复2~3直到ij,返回该位置midi,该位置正好为pivot元素。 完成一趟排序后以mid为界将序列分为两部分左序列都比pivot小有序列都比pivot大然后再分别对这两个子序列进行快速排序。以序列30245581836124239为例进行演示1、初始化ilow,jhigh,pivotR[low]30 2、从后往前找小于等于pivot的数找到R[j]12R[i]与R[j]交换i3、从前往后找大于pivot的数找到R[i]58 R[i]与R[j]交换j--4、从后往前找小于等于pivot的数找到R[j]18 R[i]与R[j]交换i5、从前往后找大于pivot的数这时ij,第一轮排序结束返回i的位置midi 此时已mid为界将原序列一分为二左子序列为1224518元素都比pivot小右子序列为36584239元素都比pivot大。然后在分别对两个子序列进行快速排序最后即可得到排序后的结果。 复杂度分析最好的时间复杂度为O(nlogn) 分解划分函数需要扫描每个元素每次扫描元素不超过n时间复杂度为O(n) 解决子问题在理想的情况下每次划分将问题分解为两个规模为n/2的子问题递归求解两个规模的子问题。所需时间为2T(n/2) 合并因为是原地排序合并不需要时间复杂度 因此总运行时间为T(n){ O(1) , n12T(n/2)O(n) , n1 }最终求解为最好的时间复杂度为O(nlogn)最坏的时间复杂度为: O(n²) 分解划分函数需要扫描每个元素每次扫描元素不超过n时间复杂度为O(n) 解决子问题在最坏的情况下每次划分将问题分解后基准元素的一侧没有元素其中一侧为规模为n-1的子问题递归求解该子问题所需时间为T(n-1)。 合并因为是原地排序合并不需要时间复杂度 因此总运行时间为T(n){ O(1) , n1T(n-1)O(n) , n1 }最终求解为最好的时间复杂度为O(n²)平均时间复杂度为O(nlogn)平均空间复杂度为O(logn)python实现def 博主GitHub page地址影zhan123.xin
