QuickSort 快速排序算法应用返回数组第k个大小的值

旺旺家 · 发表于 2014-10-15 08:42

to 香川老师，我的一维下料优化问题，您是怎么做出来的，能教下我吗？期待。多谢！
http://club.excelhome.net/home.p ... =thread&view=me

香川群子 · 发表于 2015-4-24 11:50

研究了一下，进一步开发得到如下QuickSort排序算法：

对于一维数组，返回排序后在k1~k2区间内的值，但并不需要对全部元素进行排序。
（区间内的值，可以排序，也可以不排序。）

用法：
当数据量极大，但仅仅需要提取少部分数据，且无需精确排序时非常有用、高效。

Function QuickSort(tr, l&, u&, k1&, k2&, Optional z& = 0) 'A-Z
Dim i&, j&, r, t
i = l: j = u: r = tr((l + u) \ 2)
Do
Do While i < u
If tr(i) < r Then i = i + 1 Else Exit Do
Loop
Do While j > l
If tr(j) > r Then j = j - 1 Else Exit Do
Loop
If i < j Then t = tr(i): tr(i) = tr(j): tr(j) = t: i = i + 1: j = j - 1 Else If i = j Then i = i + 1: j = j - 1: Exit Do Else Exit Do
Loop
If z Then
If k1 < j + 1 Then If j > l Then Call QuickSort(tr, l, j, k1, k2, z)
If k2 > i - 1 Then If i < u Then Call QuickSort(tr, i, u, k1, k2, z)
If k1 = k2 Then QuickSort = tr(k1)
Else
If l < k1 Then If k1 <= j Then Call QuickSort(tr, l, j, k1, k2, z)
If k1 <= l Then If l <= k2 Then If k2 < j Then Call QuickSort(tr, l, j, k1, k2, z)
If i - 1 < k1 Then If k1 <= u Then Call QuickSort(tr, i, u, k1, k2, z)
If k1 <= i - 1 Then If i - 1 <= k2 Then If k2 < u Then Call QuickSort(tr, i, u, k1, k2, z)
End If
End Function

复制代码

递归函数过程QuickSort(tr, l&, u&, k1&, k2&, Optional z& = 0)中，
第1参数 tr为待处理的一维数组。参照引用。（过程执行后源数组的顺序就会改变）
第2、第3参数 l、u 为需要排序提取的该一维数组的下标起始、结束位置。
第4、第5参数 k1、k2 为需要提取区间值的起始、结束位置。
第6参数 z 默认=0时仅提取排序区间值，但k1~k2区间内的值仍是散乱的，没做精确排序。
z=1时，会对k1~k2区间内的值做A-Z升序排序，但其余部分是不做排序的。

区间内虽然不做排序，但区间内的值总是符合比小值区间内所有值都大、比大值区间内所有值都小。
也就是说，是把整个一维数组分为小、中、大值的三个区间，但并不对所有值进行排序的算法。

香川群子 · 发表于 2016-1-17 14:38

本帖最后由香川群子于 2016-1-18 09:26 编辑

这样更好一些。
加入了<10时直接比较插入排序、提高速度效率。
另外，楼上代码在区间内不排序时排序范围有bug会造成死循环溢出堆栈、已经确认修改。

Function QuickSort(tr, l&, u&, k1&, k2&, Optional z& = 0) 'A-Z
Dim i&, j&, r, t
' cnt = cnt + 1
If u - l < 10 Then
For i = l + 1 To u
r = tr(i)
For j = i - 1 To l Step -1
If tr(j) <= r Then Exit For Else tr(j + 1) = tr(j) '<= A-Z
Next
tr(j + 1) = r
Next
Else
i = l: j = u: r = tr((l + u) \ 2)
While i < j
While tr(i) < r: i = i + 1: Wend '< A-Z
While tr(j) > r: j = j - 1: Wend 'A-Z
If i <= j Then t = tr(i): tr(i) = tr(j): tr(j) = t: i = i + 1: j = j - 1
Wend
' Debug.Print tr(k1); tr(k2); l; j; i; u; cnt
If z Then 'Sort [k1,k2]
If l < j Then If k1 <= j Then Call QuickSort(tr, l, j, k1, k2, z)
'l,k1,j,k2/k1,l,k2,j/k1,l,j,k2/ Not l,j,k1,k2
If i < u Then If i <= k2 Then Call QuickSort(tr, i, u, k1, k2, z)
'i,k1,u,k2/k1,i,k2,u/k1,i,u,k2/ Not k1,k2,i,u
Else 'No Sort [k1,k2]
If l < j Then If l < k1 Then If k1 <= j Then Call QuickSort(tr, l, j, k1, k2, z)
'l<k1,(k1<=j),(k2)
If l < j Then If k1 < l Then If k2 < j Then Call QuickSort(tr, l, j, k1, k2, z)
'k1<l,(k2<j)
If i < u Then If i < k1 Then If u <= k2 Then Call QuickSort(tr, i, u, k1, k2, z)
'(i<k1),u<=k2
If i < u Then If i < k2 Then If k2 < u Then Call QuickSort(tr, i, u, k1, k2, z)
'(k1),(i<k2),k2<u
End If
End If
If k1 = k2 Then QuickSort = tr(k1)
End Function

复制代码

cui26896 · 发表于 2019-6-17 22:54

本帖最后由 cui26896 于 2019-6-18 08:02 编辑

要是对二维数组中的一列也能做就好了。

cui26896 · 发表于 2019-6-21 17:22

复制代码运行后，字符形查找第一位中间还是隔了一个D，如附件所示。
Inked运行结果_LI.jpg

weiliang2018 · 发表于 2021-4-25 11:34

香川群子发表于 2016-1-17 14:38
这样更好一些。
加入了

有没有按照平均值作为key中轴的代码

香川群子 · 发表于 2021-4-25 12:14

weiliang2018 发表于 2021-4-25 11:34
有没有按照平均值作为key中轴的代码

是否采用算术平均值作为区分中轴的算法，和随机取值或取个数中间值，实际运用之后的耗时差异并没有很大。

也就是说，几乎没影响。

原因就是，不管怎么折腾，该走的步骤并不会因此减少。
因为这个是递归计算的，如果某个区段直接都是大数值或小数值，还是需要反复递归迭代计算的。

你不用在此费心了。……如果真的有显著提升效率的作用，那么多比你聪明的人，早就更改代码了。
全世界都没你聪明，是绝对不可能的。

weiliang2018 · 发表于 2021-4-25 21:27

香川群子发表于 2021-4-25 12:14
是否采用算术平均值作为区分中轴的算法，和随机取值或取个数中间值，实际运用之后的耗时差异并没有很大。 ...

之前1892不是有个排序算法帖子，里面有个版主发个链接说按照平均值排序，说好像更稳定了，不受已排序影响。

香川群子 · 发表于 2021-4-26 19:27

weiliang2018 发表于 2021-4-25 21:27
之前1892不是有个排序算法帖子，里面有个版主发个链接说按照平均值排序，说好像更稳定了，不受已排序影响 ...

不可能。平均值又不是中位数。

其实效率最高的应该是中位数。
但是计算求中位数也要消耗计算时间和效率的，没有实际价值。

我已经说的很清楚了，如果确实有好处，而且不是特例（和数据本身特征有关）是普遍有效，那么代码早就改过来了。

到此e游 · 发表于 2024-6-23 09:33

多谢！慢慢学习，领会中。

		自动登录	找回密码
密码			免费注册

[原创] QuickSort 快速排序算法应用 返回数组第k个大小的值

[原创] QuickSort 快速排序算法应用返回数组第k个大小的值