package Ġchapter 5 . section 1 Ċ Ċ import Ġchapter 2 . section 1 . insertion Sort Ċ import Ġextensions . shuffle Ċ Ċ /** Ċ Ġ* Ġ äºļ çº¿ æĢ§ æİĴåºı Ċ Ġ* Ġ ç¼ĸåĨĻ ä¸Ģä¸ª å¤ĦçĲĨ Int åĢ¼çļĦ æİĴåºı ç®Ĺæ³ķ ï¼Į éģįåİĨ æķ°ç»Ħ ä¸¤ éģį ï¼Į ç¬¬ä¸Ģ éģį æł¹æį® æīĢæľī éĶ® çļĦ é«ĺ 1 6 ä½į è¿Ľè¡Į ä½İ ä½į ä¼ĺåħĪ çļĦ æİĴåºı ï¼Į ç¬¬äºĮ éģį è¿Ľè¡Į æıĴåħ¥ æİĴåºı ãĢĤ Ċ Ġ* Ċ Ġ* Ġ è§£ ï¼ļ å¯¹ é«ĺ 1 6 ä½į è¿Ľè¡Į ä½İ ä½į ä¼ĺåħĪ æİĴåºı åĲİ ï¼Į æıĴåħ¥ æİĴåºı ä¼ļ è¢« åĪĨ åī² ä¸º å¤ļä¸ª çĭ¬ç«ĭ çļĦ åĮº éĹ´ ï¼Į æ¯ıä¸ª åĮº éĹ´ æľĢ å¤ļ æľī 2 ^ 1 6 = 6 5 5 3 6 ä¸ª ä¸įåĲĮ çļĦåĢ¼ Ċ Ġ* Ġæı Ĵ åħ¥ æİĴåºı åľ¨ å°ı èĮĥåĽ´ åĨħ çļĦ æĢ§èĥ½ ä¸į éĶĻ Ċ Ġ*/ Ċ fun Ġex 1 5 _ Sub linear Sort ( array : ĠArray < Int >) Ġ{ ĊĠĠĠ Ġex 1 5 _ H ight 1 6 Bit Sort ( array ) ĊĠĠĠ Ġinsertion Sort ( array ) Ċ } Ċ Ċ /** Ċ Ġ* Ġå¯¹ Int çļĦ é«ĺ 1 6 ä½į è¿Ľè¡Į ä½İ ä½į ä¼ĺåħĪ æİĴåºı Ċ Ġ* Ċ Ġ* Ġ å¦Ĥä½ķ åĪ¤æĸŃ ç¬¬ d ä½į çļĦåĢ¼ ï¼ļ å°Ĩ 1 å·¦ ç§» d - 1 ä½į ï¼Į ä¸İ åİŁ åĢ¼ æĮī ä½į ä¸İ è¿Ĳç®Ĺ ï¼Į èĭ¥ åĢ¼ä¸º 0 ï¼Į åĪĻ ç¬¬ d ä½į ä¸º 0 ï¼Į åĢ¼ éĿŀ 0 åĪĻ ç¬¬ d ä½į ä¸º 1 Ċ Ġ* Ġ å¯¹äºİ ç¬¬ 1 6 ~ 3 1 ä½į ï¼Į 0 æ¯Ķ 1 å°ı ï¼Į 0 æİĴ åľ¨ 1 åīį éĿ¢ ï¼Į å¯¹äºİ ç¬¬ 3 2 ä½į ç¬¦ åı· ä½į æĿ¥è¯´ ï¼Į 1 æİĴ åľ¨ 0 åīį éĿ¢ ï¼Į åĽłä¸º 1 ä»£è¡¨ è´Ł æķ° Ċ Ġ*/ Ċ fun Ġex 1 5 _ H ight 1 6 Bit Sort ( array : ĠArray < Int >) Ġ{ ĊĠĠĠ Ġval Ġaux Ġ= ĠArray ( array . size ) Ġ{ Ġ 0 Ġ} ĊĠĠĠ Ġ// Ġä½¿çĶ¨ ä¸¤ä¸ª åıĺéĩı ä»£ æĽ¿ count æķ°ç»Ħ ĊĠĠĠ Ġvar Ġx Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġy Ġ= Ġ 0 ĊĠĠĠ Ġfor Ġ( d Ġin Ġ 1 6 .. 3 2 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġbase Ġ= Ġ 1 Ġshl Ġ( d Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġx Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġy Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ// Ġ ç»Łè®¡ 0 åĴĮ éĿŀ 0 çļĦ æĢ» æķ° ĊĠĠĠĠĠĠĠ Ġarray . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġit Ġand Ġbase ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d Ġ== Ġ 3 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ å¯¹äºİ ç¬¬ 3 2 ä½į ç¬¦ åı· ä½į æĿ¥è¯´ ï¼Į 1 æ¯Ķ 0 å°ı ï¼Į 1 æİĴ åľ¨ åīį éĿ¢ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== Ġ 0 ) Ġy ++ Ġelse Ġx ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ å¯¹äºİ åħ¶ä»ĸ ä½į æĿ¥è¯´ ï¼Į 0 æ¯Ķ 1 å°ı ï¼Į 0 æİĴ åľ¨ åīį éĿ¢ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== Ġ 0 ) Ġx ++ Ġelse Ġy ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġå°Ĩ æĢ» æķ° è½¬æį¢ ä¸º ç´¢å¼ķ ĊĠĠĠĠĠĠĠ Ġy Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġx Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġarray . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġarray [ i ] Ġand Ġbase ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d Ġ== Ġ 3 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ç¬¬ 3 2 ä½į æĿ¥è¯´ ï¼Į y ä»£è¡¨ 0 çļĦ ç´¢å¼ķ ï¼Į x ä»£è¡¨ 1 çļĦ ç´¢å¼ķ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaux [ y ++] Ġ= Ġarray [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaux [ x ++] Ġ= Ġarray [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaux [ x ++] Ġ= Ġarray [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaux [ y ++] Ġ= Ġarray [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġarray . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ i ] Ġ= Ġaux [ i ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġ// Ġkotlin ä¸Ń å¦Ĥæŀľ ç¬¬ 3 2 ä½į ä¸º 1 åĪĻ ä¼ļ è¢« æİ¨ å¯¼ ä¸º Long ç±»åŀĭ ï¼Į èĢĮä¸įæĺ¯ è´Ł æķ° ï¼Į Java ä¸Ń åı¯ä»¥ æİ¨ å¯¼ ä¸º int ç±»åŀĭçļĦ è´Ł æķ° ĊĠĠĠ Ġval Ġarray Ġ= ĠarrayOf < Int >( ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 xFFFFFFFF . toInt (), Ġ// Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x FFFFFF FE . toInt (), Ġ// Ġ- 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 8 0 0 0 0 0 0 0 . toInt (), Ġ// ĠInt . MIN _ VALUE Ġ- 2 1 4 7 4 8 3 6 4 8 ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 xF 0 0 0 FFFF . toInt (), ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 xFF 0 FFFF F . toInt (), ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 xFF 1 FFFF F . toInt (), ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 xFF 2 FFFF F . toInt (), ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 xFF 2 FFFF 0 . toInt (), ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 7 FFFF FFF , Ġ// ĠInt . MAX _ VALUE Ġ 2 1 4 7 4 8 3 6 4 7 ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 7 C FFFFFF , ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 7 C FFFF F 0 , ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 1 0 0 0 0 0 0 0 , ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 0 0 0 0 0 0 0 0 , Ġ// Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 0 0 0 0 0 0 0 1 , Ġ// Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 x 0 0 0 0 0 0 0 2 Ġ Ġ// Ġ 2 ĊĠĠĠ Ġ) ĊĠĠĠ Ġ// Ġ éļıæľº æīĵ ä¹± æķ°ç»Ħ ĊĠĠĠ Ġarray . shuffle () ĊĠĠĠ Ġex 1 5 _ Sub linear Sort ( array ) ĊĠĠĠ Ġprintln ( array . join ToString ( separator Ġ= Ġ"\ n ")) Ċ }