Stooge-sort(A, i, j)
if A[i] > A[j]
then exchange A[i], A[]
if i + 1 >= j
then return
k = (j - i + 1) / 3
Stooge-sort(A, i, j - k)
Stooge-sort(A, i + k , j)
Stooge-sort(A, i, j - k)
即先排序前2/3部分,然后是后2/3部分,最后再进行前面1/3的排序。
a. 证明算法正确性
由于是递归算法,而初始状态显然成立,因此只要证明当部分排序正确时,整体也能够被正确排序:
第一次排序后,第二部分每个数都不小于第一部分的所有数;
第二次排序后,第二部分某些数被交换到第三部分中,此时第三部分数都不小于第二部分和第一部分的数,但是第二部分的数并不一定都小于第一部分的(因为可能包含第三部分的数,而这些数与第一部分数的大小关系无法确认);
第三次排序后,第二部分的数都不小于第一部分的数。
这样,第一部分的任意数<=第二部分的任意数<=第三部分的任意数
而且各部分的数都已排序,因此整体已被排序。
b. 复杂度分析
递归式
T(n) = 3T(2n/3) + 1
由Master Theorem
T(n) = O(n^log(3/2, 3))
分享到:
相关推荐
JAVA实现StoogeSort方法排序,简单演示。
this program is stooge_sort that writted with c++. this program get an array and sort it in order nlogn.
指示用于命令行npm install -g email-stoogeemail-stooge --help用于程序化用途npm install -g email-stooge var stooge = require ( 'stooge' ) ;stooge ( { sourceDir : '/path/to/templates' , distDir : '/path/...
桶排序算法,分治算法,输入一串数字,输出他们从小到大的排序
例如,在问题 12 中,使用了 StoogeSort 算法来对数据进行排序。StoogeSort 算法的时间复杂度为 O(n^2.7095)。 8. 时间复杂度分析 时间复杂度分析是算法设计中的一种重要概念,用于衡量算法的执行效率。例如,在...
* ②当递归执行 StoogeSort(left+k,right);时,使序列的后 2/3 的子序列有序,经过这两次递归排序,使原序列的后 1/3 的位置上是整个序列中较大的数,即序列后 1/3 的位置上数均大于前 2/3 的数,但此时,前 2/3 的...
* 排序算法:了解StoogeSort算法的正确性证明,了解递归排序的方法。 * 时间复杂度分析:了解冒泡排序、堆排序、快速排序的最坏时间复杂度,比较不同排序算法的时间复杂度。 第十三章 * 选取算法:了解select算法...