题意不清啊,输出原始下标是什么意思?有点费解。
最近做了几种排序的比较,对10000个正整数排序(未编译情况下):冒泡法6260ms,选择法2520ms,计数法13ms,快速排序法47ms。
由于计数法只能对正整数排序,且最大正整数还不能太大,所以不实用,排序还是用快速排序效果好。
快速排序的思想是:在排序系列中取一个数(可随机取),其他数与这个数比较,大于的在右边,小于的在左边,然后用递归方法对左边和右边再取数分治,最终左右位置相等时依次退出递归。代码如下:
private sub QuickSort(a() as integer,l as integer,r as integer)
dim i as integer,j as integer,key as integer,t as integer
if l<lbound(a) or r>ubound(a) then exit sub '如果数组左右下标超出数组范围则退出
key = a((l + r) \ 2) '取数组中间数做key值
i=l:j=r
while i<=j
while a(i)<key and i<r
'此循环找到左边第一个大于key值的数
i=i+1
wend
while a(j)>key and j>l
'此循环从最右边找小于key值的数,这两个循环不要用for循环,虽然for循环也可达到目的,但每次都会重复从最左边和最右边计数,加大了排序时间
j=j-1
wend
'经过上两个循环,i所在位置的数是大于key,而j所在位置的数小于key,两数交换即符合快速排序分治的要求
if i<=j then
'a(i)、a(j)两数通过中间变量t交换
t=a(i):a(i)=a(j):a(j)=t
i=i+1:j=j-1
endif
wend
if l<j then quicksort a,l,j '嵌套做左边快速排序
if r>i then quicksort a,i,r '嵌套做右边快速排序
end sub
[
本帖最后由 lowxiong 于 2013-4-25 22:34 编辑 ]