Board logo

标题: 【练习-014】出给新手的数值排序加分题 [打印本页]

作者: pusofalse    时间: 2008-8-20 22:39     标题: 【练习-014】出给新手的数值排序加分题

出题目的:
        掌握任意数列之间的排序技巧
解题要求:
        代码通用、高效
        尽量简洁
        尽量不生成临时文件
加分规则:
        1 思路独特基准分5分
        2 代码高效、通用基准分4分
        3 技巧高超基准分3分
        4 代码简洁基准分2分
        5 完美代码加分15分
题目如下:
        给出任意一组数列,正序输出,如:
        3 2008 11 19 777 23 2014 453 789 51
        输出为:3 11 19 23 51 453 777 789 2008 2014
说明:
        不必考虑特大数,所给的数列中都是整数值。
作者: lzwudi    时间: 2008-8-21 00:00

没明白LZ的意思呀,,
作者: dishuo    时间: 2008-8-21 00:15

下午刚写了个快速排序,正好用上啦.冒泡就不写了.
cls&@echo off&setlocal enabledelayedexpansion
set "strings=3 2008 11 19 777 23 2014 453 789 51"
echo %strings%
set/a n=0
for %%i in (%strings%) do (
   
set/a n+=1
   
set num[!n!]=%%i
)
call :quicksort num 1 %n%
for /l %%i in (1,1,%n%) do echo !num[%%i]!

pause&goto:eof

:QuickSort
::code by dishuostec
::use call :quicksort arrary low high
set "ARR=%1"
set/a dep=0
call :QS %2 %3
goto:eof
:QS
set/a dep+=1,lTmpLow=%1,lTmpHi=%2,Low=%1,Hi=%2
if %Hi% leq %Low% set/a dep-=1&goto :eof
set/a lTmpMid=(Low+Hi)/2
call set/a vTempVal=%%%ARR%[!lTmpMid!]%%
:qsMainLoop
if !lTmpLow! leq !lTmpHi! (
   
:qsLoop1
   
call set/a vVal=%%%ARR%[!lTmpLow!]%%
   
if !vVal! lss !vTempVal! if !lTmpLow! lss !Hi! set/a lTmpLow+=1& goto qsLoop1
   
:qsLoop2
   
call set/a vVal=%%%ARR%[!lTmpHi!]%%
   
if !vTempVal! lss !vVal! if !Low! lss !lTmpHi! set/a lTmpHi-=1&goto qsLoop2
   
:qsSwap
   
if !lTmpLow! leq !lTmpHi! (
        
call set/a vTmpHold=%%%ARR%[!lTmpLow!]%%
        
call set/a %ARR%[!lTmpLow!]=%%%ARR%[!lTmpHi!]%%
        
set/a %ARR%[!lTmpHi!]=vTmpHold
        
set/a lTmpLow+=1,lTmpHi-=1
    )
goto qsMainLoop
)
set/a lTmpLow[%dep%]=lTmpLow,Hi[%dep%]=Hi
if %Low% lss %lTmpHi% call :QS %Low% %lTmpHi%
call set lTmpLow=%%lTmpLow[!dep!]%%&call set Hi=%%Hi[!dep!]%%
if %lTmpLow% lss %Hi% call :QS %lTmpLow% %Hi%
set/a dep-=1&goto :eof

作者: batman    时间: 2008-8-21 10:34

代码写的实在是繁杂。。。
作者: huahua0919    时间: 2008-8-21 11:16

写这么长也很不错了
作者: dishuo    时间: 2008-8-21 12:14

嫌代码长可以用冒泡法,但是数据量大的时候效率比快速排序低.
另外,我写的这两种排序都是通用模块,移植的拷过去就行.
cls&@echo off&setlocal enabledelayedexpansion
set "strings=3 2008 11 19 777 23 2014 453 789 51"
echo %strings%
set/a n=0
for %%i in (%strings%) do (
   
set/a n+=1
   
set num[!n!]=%%i
)
call :popsort num 1 %n%
for /l %%i in (1,1,%n%) do echo !num[%%i]!
pause&goto:eof

:PopSort
::code by dishuostec
::use call :PopSort arrary low highset "ARR=%1"
set /a PS_l=%3
for /l %%i in (%2,1,%3) do (
   
set/a PS_l-=1
   
for /l %%j in (%2,1,!PS_l!) do (
        
set/a PS_index2=%%j+1
        
call set PS_v1=%%%ARR%[%%j]%%&call set PS_v2=%%%ARR%[!PS_index2!]%%
        
if !PS_v1! gtr !PS_v2! set %ARR%[!PS_index2!]=!PS_v1!&set %ARR%[%%j]=!PS_v2!
    )
)

作者: terse    时间: 2008-8-21 14:01

还是用补位效率高
  1. @echo off&setlocal enabledelayedexpansion
  2. set str=3 2008 11 19 777 23 2014 453 789 51
  3. for %%i in (%str%) do (
  4.     set str=0000000000%%i
  5.     set .!str:~-10! !random!=%%i
  6. )
  7. for /f "tokens=2 delims==" %%i in ('set .') do set/p=%%i <nul
  8. pause>nul
复制代码

作者: pusofalse    时间: 2008-8-21 14:02

terse前辈,应该把这题留给新人做。^_^
作者: 基拉freedom    时间: 2008-8-21 14:29

我的
~~~~~~~用了sort
  1. @echo off
  2. setlocal EnableDelayedExpansion
  3. set n=0
  4. for %%i in (3 2008 11 19 777 23 2014 453 789 51) do (
  5. set/a n+=1
  6. set str[!n!]=   %%i
  7. )
  8. for /l %%i in (1,1,%n%) do echo !str[%%i]:~-4!>>1.txt
  9. sort 1.txt
  10. set /p a=按回车键结束
  11. del 1.txt
复制代码
测试通过
作者: pusofalse    时间: 2008-8-21 16:07     标题: 回复 9楼 的帖子

echo !str[%%i]:~-4! 这里出现了问题,如果是个5位数呢。
测试如下:
for /l %%a in (1 1 10) do set "var=!var!!random! "
for %%i in (%var%) do (
.......
......
你的代码就会出错了。还能再精简,也用不到临时文件。

[ 本帖最后由 pusofalse 于 2008-8-21 16:26 编辑 ]
作者: 基拉freedom    时间: 2008-8-21 16:43


精简直接用 |sort 就可以了 我知道 但就不知道该加在哪~~呵呵
那个~ 可以用扩展的大一点 我这样做是为了符合题意o(∩_∩)o...
作者: pusofalse    时间: 2008-8-21 16:46

sort 1.txt无异于
(echo   123&echo 12345&echo    23)|sort
作者: start    时间: 2008-8-21 21:17

@echo off
echo 没排前
echo 3 2008 11 19 777 23 2014 453 789 51
echo,
echo 排列后
for /f "tokens=1-10 delims= " %%a in ("3 2008 11 19 777 23 2014 453 789 51") do echo %%a %%c %%d %%f %%j %%h %%e %%i %%b %%g
pause>nul

版主这样行不???学批2天,瞎弄``哈哈

[ 本帖最后由 start 于 2008-8-21 21:21 编辑 ]
作者: 523066680    时间: 2008-8-21 21:47

来一个偏方 虽然显示不慢 但理论上效率不高 不介意吧 o(∩_∩)o 只是偏方
@echo off
for %%a in (3 2008 11 19 777 23 2014 453 789 51) do set _%%a=exist
for /l %%a in (1,1,3000) do (if defined _%%a call,set n=%%n%% %%a)
echo %n%
pause

[ 本帖最后由 523066680 于 2008-8-21 21:51 编辑 ]
作者: 523066680    时间: 2008-8-22 07:06

原帖由 terse 于 2008-8-21 14:01 发表
还是用补位效率高
…… set .!str:~-10! !random!=%%i……

这里random是否起着一定作用。
作者: 523066680    时间: 2008-8-22 08:53

问题出来了,
虽然偏方的代码不长,但是如果排序的数字 有几个是相同滴咋办
作者: mkl    时间: 2008-8-22 09:04

不知是否符合题意
  1. @echo off&setlocal enabledelayedexpansion
  2. set "p=3 2008 11 19 777 23 2014 453 789 51"
  3. for %%i in (%p%) do (
  4.    set t=1
  5.    for %%r in (%p%) do (
  6.        if %%i gtr %%r set /a t=!t!+1
  7.    )
  8. set !t!=%%i
  9. )
  10. echo !1! !2! !3! !4! !5! !6! !7! !8! !9! !10!
  11. pause
复制代码

作者: batman    时间: 2008-8-22 10:37     标题: 先来两种方法

一、冒泡法:
  1. @echo off&setlocal enabledelayedexpansion
  2. for %%i in (3 2008 11 19 777 23 2014 453 789 51) do set "str=!str! #%%i#"
  3. set "var=%str%"
  4. for %%a in (%str%) do (
  5.     for %%i in (!var!) do (
  6.         set "a=%%a"&set "b=%%i"
  7.         set "a=!a:#=!"&set "b=!b:#=!"
  8.         if !a! gtr !b! (
  9.         set "var=!var:%%a =!"
  10.         set "var=!var:%%i=%%i %%a!"
  11.         )
  12.     )
  13. )
  14. echo %var:#=%&pause>nul
复制代码
二、补位法:
  1. @echo off&setlocal enabledelayedexpansion
  2. for /l %%i in (1,1,80) do set "bw=!bw!0"
  3. for %%i in (3 2008 11 19 777 23 2014 453 789 51) do (
  4.      set "str=%bw%%%i"
  5.      set "_!str:~-80!=%%i"
  6. )
  7. for /f "tokens=2 delims==" %%i in ('set _') do set /p=%%i <nul
  8. pause>nul
复制代码

[ 本帖最后由 batman 于 2008-8-22 14:18 编辑 ]
作者: 基拉freedom    时间: 2008-8-22 10:37

好了
根据版主所说改进了一下
还是用了临时文件 不改了 ~~ ~  通用性增强 最大到10位~~
  1. @echo off
  2. setlocal EnableDelayedExpansion
  3. echo 数组排列
  4. echo.
  5. echo 最大可支持10位 输入时以空格键隔开
  6. echo.
  7. set /p str=输入数组:
  8. echo.
  9. echo 原数组为%str%.
  10. set n=0
  11. for %%i in (%str%) do (
  12. set/a n+=1
  13. set str[!n!]=         %%i
  14. )
  15. for /l %%i in (1,1,%n%) do echo !str[%%i]:~-10!>>1.txt
  16. echo.
  17. echo.
  18. echo 现数组为:
  19. sort 1.txt
  20. set /p a=按回车键结束
  21. del 1.txt
复制代码

作者: batman    时间: 2008-8-22 10:45

原帖由 mkl 于 2008-8-22 09:04 发表
不知是否符合题意@echo off&setlocal enabledelayedexpansion
set "p=3 2008 11 19 777 23 2014 453 789 51"
for %%i in (%p%) do (
   set t=1
   for %%r in (%p%) do (
       if %%i gtr %%r set /a t=!t!+ ...

修改成如下可使代码通用些:
  1. @echo off&setlocal enabledelayedexpansion
  2. set "p=3 2008 11 19 777 23 2014 453 789 51"
  3. for %%i in (%p%) do (
  4.    set /a n+=1,t=1
  5.    for %%r in (%p%) do (
  6.        if %%i gtr %%r set /a t+=1
  7.    )
  8.    set !t!=%%i
  9. )
  10. for /l %%i in (1,1,%n%) do set /p=!%%i! <nul
  11. pause>nul
复制代码

[ 本帖最后由 batman 于 2008-8-22 10:51 编辑 ]
作者: 523066680    时间: 2008-8-22 14:40

以上部分代码考虑了相同的数 有的没有考虑 。有相同的数 只显示了一次。
(嘿!!!!凭什么我写那个跟你想的¥!@#%@##~!#        就只加我2分啊)

[ 本帖最后由 523066680 于 2008-8-23 11:41 编辑 ]
作者: pusofalse    时间: 2008-8-22 15:00

只需把9楼的代码稍作调整即可。
  1. @echo off
  2. setlocal EnableDelayedExpansion
  3. for /l %%a in (1 1 10) do set "var=!var!!random! "
  4. echo %var%%
  5. for %%i in (%var%) do (
  6. set "str=   %%i"
  7. set "echo=!echo!echo !str:~-5!&"
  8. )
  9. (%echo:~,-1%)|sort
  10. pause>nul
复制代码

[ 本帖最后由 pusofalse 于 2008-8-22 15:03 编辑 ]
作者: 523066680    时间: 2008-8-23 11:35

居然没人理我也……17楼的思路是可以完善到 存在重复的数的,
(呜呜 我读书的时候想过这个思路的 估计false也不会考虑给我加分了)
以下是17楼思路的更新版本  允许存在相同的数
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. set hang=3 2008 11 19 777 23 2014 453 789 51 3 3 4 2014
  4. set n=0
  5. for %%a in (%hang%) do (
  6.   set /a num=1,n+=1
  7.   for %%b in (%hang%) do (
  8.     if %%a gtr %%b set /a num+=1
  9.   )
  10. call :next !num!
  11. set !num!=%%a
  12. )
  13. for /l %%a in (1,1,%n%) do echo !%%a!
  14. pause
  15. goto :eof
  16. :next
  17. if defined %num% (set /a num+=1 &goto :next)
复制代码

[ 本帖最后由 523066680 于 2008-8-23 11:37 编辑 ]
作者: 基拉freedom    时间: 2008-8-23 12:10

原帖由 523066680 于 2008-8-22 14:40 发表
以上部分代码考虑了相同的数 有的没有考虑 。有相同的数 只显示了一次。
(嘿!!!!凭什么我写那个跟你想的¥!@#%@##~!#        就只加我2分啊)

这倒是的~~呵呵~~~
作者: itrui    时间: 2008-8-23 20:50

有些地方正好对我工作有点用处。

[ 本帖最后由 itrui 于 2008-8-23 21:03 编辑 ]
作者: CZT    时间: 2008-8-26 14:34

哈哈
看到这篇贴子
我知道了有一个叫冒泡排序的东西
另外Batcher兄在另外一个贴子里面给了一个学习冒泡排序的连接
让我好好的学习了一把
我现在把它帮到这里来
希望不懂什么叫冒泡排序的朋友也去学习下
http://www.google.cn/search?hl=z ... %E5%BA%8F&meta=
作者: 愚无尽    时间: 2008-8-26 18:38

居然才是新手的题目,哎,看来。。。
作者: sunraojian    时间: 2012-8-19 21:50

回复 7# terse


    那个set .是什么意思?




欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2