php网站截图,常州教育建设装备中心网站,专业简历怎么填,wordpress 主题替换基本思想#xff1a;
任取一个元素#xff08;比如第一个#xff09;为中心#xff0c;称为枢轴#xff08;pivot#xff09;所有比它小的元素一律前放#xff0c;比它大的元素后放#xff0c;形成左右两个子表对各子表重新选择中心元素并以此规则调整直到每个子表的元…基本思想
任取一个元素比如第一个为中心称为枢轴pivot所有比它小的元素一律前放比它大的元素后放形成左右两个子表对各子表重新选择中心元素并以此规则调整直到每个子表的元素只剩一个
算法
void QSort(SqList L, int low, int high){if(lowhigh){pivotloc Partition(L,low, high);//将L.r[]一分为二pivotloc为枢轴元素排好序的位置QSort(L, low, pivotloc-1);//对左子表递归排序QSort(L, pivotloc1, high);//对右子表递归排序}
}int Partition(SqList L, int low, int high){L.r[0]L.r[low];pivotkey L.r[low].key;while(lowhigh){while(lowhigh L.r[high.key]pivotkey)--high;L.r[low]L.r[high];while(lowhigh L.r[low.key]pivotkey)low;L.r[high] L.r[low];}L.r[low]L.r[0];return low;
}示例 对于序列49 38 65 97 76 13 27进行快速排序步骤如下 以第一个元素49作为枢轴即pivotkey49进行第一轮排序最后一个元素开始将序列中大于49的元素放在右边小于49的元素放在左边
2749将27放在左侧 i 所指的位置上i 384938放在左侧i的位置上已处在合适的位置i 6549将65放在右侧 j 所指的位置上j-- 1349将13放在左侧 i 所指的位置上i 以此类推直到 ij用枢轴pivotkey替换此时的 i 和 j 的位置 第一轮排序过程如下 第一轮排序后由于左右子序列元素个数均大于1继续对左右子序列排序
对左子序列排序 选第一个元素为枢轴 排序过程如下 经过一趟快排之后左右子序列的元素个数均为1左子序列排序结束
对右子序列排序 选第一个元素为枢轴 排序过程如下: 经过一趟快排之后左右子序列的元素个数均为1右子序列排序结束
排序结束生成的有序序列为13 27 38 49 65 76 97
时间复杂度
O( n l o g 2 n nlog_2n nlog2n)
QSort():Q( l o g 2 n log_2n log2n)Partition()O(n)
就平均计算时间而言快速排序是所有内排序方法中最好的一个
空间复杂度
快速排序不是原地排序
由于程序使用了递归需要递归调用栈的支持而栈的长度取决于递归调用的深度
平均情况下需要O(logn)的空间最坏情况下需要O(n)的空间
稳定性
快速排序是一种不稳定的排序方法
